188 research outputs found
On the Number of Embeddings of Minimally Rigid Graphs
Full text linkRigid frameworks in some Euclidian space are embedded graphs having a unique
local realization (up to Euclidian motions) for the given edge lengths,
although globally they may have several. We study the number of distinct planar
embeddings of minimally rigid graphs with vertices. We show that, modulo
planar rigid motions, this number is at most . We also exhibit several families which realize lower bounds of the order
of , and .
For the upper bound we use techniques from complex algebraic geometry, based
on the (projective) Cayley-Menger variety over the complex numbers . In this context, point configurations
are represented by coordinates given by squared distances between all pairs of
points. Sectioning the variety with hyperplanes yields at most
zero-dimensional components, and one finds this degree to be
. The lower bounds are related to inductive
constructions of minimally rigid graphs via Henneberg sequences.
The same approach works in higher dimensions. In particular we show that it
leads to an upper bound of for the number of spatial embeddings
with generic edge lengths of the 1-skeleton of a simplicial polyhedron, up to
rigid motions
Natural realizations of sparsity matroids
Get PDFA hypergraph G with n vertices and m hyperedges with d endpoints each is
(k,l)-sparse if for all sub-hypergraphs G' on n' vertices and m' edges, m'\le
kn'-l. For integers k and l satisfying 0\le l\le dk-1, this is known to be a
linearly representable matroidal family.
Motivated by problems in rigidity theory, we give a new linear representation
theorem for the (k,l)-sparse hypergraphs that is natural; i.e., the
representing matrix captures the vertex-edge incidence structure of the
underlying hypergraph G.Comment: Corrected some typos from the previous version; to appear in Ars
Mathematica Contemporane
Slider-pinning Rigidity: a Maxwell-Laman-type Theorem
Get PDFWe define and study slider-pinning rigidity, giving a complete combinatorial
characterization. This is done via direction-slider networks, which are a
generalization of Whiteley's direction networks.Comment: Accepted, to appear in Discrete and Computational Geometr
Geometric auxetics
Get PDFWe formulate a mathematical theory of auxetic behavior based on one-parameter
deformations of periodic frameworks. Our approach is purely geometric, relies
on the evolution of the periodicity lattice and works in any dimension. We
demonstrate its usefulness by predicting or recognizing, without experiment,
computer simulations or numerical approximations, the auxetic capabilities of
several well-known structures available in the literature. We propose new
principles of auxetic design and rely on the stronger notion of expansive
behavior to provide an infinite supply of planar auxetic mechanisms and several
new three-dimensional structures
Expansive periodic mechanisms
Get PDFA one-parameter deformation of a periodic bar-and-joint framework is
expansive when all distances between joints increase or stay the same. In
dimension two, expansive behavior can be fully explained through our theory of
periodic pseudo-triangulations. However, higher dimensions present new
challenges. In this paper we study a number of periodic frameworks with
expansive capabilities in dimension and register both similarities
and contrasts with the two-dimensional case
Extremal Configurations of Hinge Structures
Get PDFWe study body-and-hinge and panel-and-hinge chains in R^d, with two marked
points: one on the first body, the other on the last. For a general chain, the
squared distance between the marked points gives a Morse-Bott function on a
torus configuration space. Maximal configurations, when the distance between
the two marked points reaches a global maximum, have particularly simple
geometrical characterizations. The three-dimensional case is relevant for
applications to robotics and molecular structures
Deformations of crystal frameworks
Get PDFWe apply our deformation theory of periodic bar-and-joint frameworks to
tetrahedral crystal structures. The deformation space is investigated in detail
for frameworks modelled on quartz, cristobalite and tridymite
Liftings and stresses for planar periodic frameworks
Get PDFWe formulate and prove a periodic analog of Maxwell's theorem relating
stressed planar frameworks and their liftings to polyhedral surfaces with
spherical topology. We use our lifting theorem to prove deformation and
rigidity-theoretic properties for planar periodic pseudo-triangulations,
generalizing features known for their finite counterparts. These properties are
then applied to questions originating in mathematical crystallography and
materials science, concerning planar periodic auxetic structures and ultrarigid
periodic frameworks.Comment: An extended abstract of this paper has appeared in Proc. 30th annual
Symposium on Computational Geometry (SOCG'14), Kyoto, Japan, June 201
Expansive Motions and the Polytope of Pointed Pseudo-Triangulations
Full text linkWe introduce the polytope of pointed pseudo-triangulations of a point set in
the plane, defined as the polytope of infinitesimal expansive motions of the
points subject to certain constraints on the increase of their distances. Its
1-skeleton is the graph whose vertices are the pointed pseudo-triangulations of
the point set and whose edges are flips of interior pseudo-triangulation edges.
For points in convex position we obtain a new realization of the
associahedron, i.e., a geometric representation of the set of triangulations of
an n-gon, or of the set of binary trees on n vertices, or of many other
combinatorial objects that are counted by the Catalan numbers. By considering
the 1-dimensional version of the polytope of constrained expansive motions we
obtain a second distinct realization of the associahedron as a perturbation of
the positive cell in a Coxeter arrangement.
Our methods produce as a by-product a new proof that every simple polygon or
polygonal arc in the plane has expansive motions, a key step in the proofs of
the Carpenter's Rule Theorem by Connelly, Demaine and Rote (2000) and by
Streinu (2000).Comment: 40 pages, 7 figures. Changes from v1: added some comments (specially
to the "Further remarks" in Section 5) + changed to final book format. This
version is to appear in "Discrete and Computational Geometry -- The
Goodman-Pollack Festschrift" (B. Aronov, S. Basu, J. Pach, M. Sharir, eds),
series "Algorithms and Combinatorics", Springer Verlag, Berli
- …
