Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell--Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

We 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 rigidity-theoretic properties for planar periodic pseudo-triangulations, generalizing 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.

Flexibility studies of macromolecules modeled as mechanical frameworks rely on computationally expensive, yet numerically imprecise simulations. Much faster approaches for degree-of-freedom counting and rigid component calculations are known for finite structures characterized by theorems of Maxwell-Laman type, but such results are exceedingly rare and difficult to obtain. The situation is even more complex for infinite, periodic structures such as those appearing in the study of crystalline materials. Here, an adequate rigidity theoretical formulation has been proposed only recently, opening the way to a combinatorial treatment.

Given a 3D polygonal chain with fixed edge lengths and fixed angles between consecutive edges (shortly, a revolute-jointed chain or robot arm), the Extremal Reaches Problem asks for those configurations where the distance between the endpoints attains a global maximum or minimum value. In this paper, we solve it with a polynomial time algorithm.

We present the first exact, combinatorial, polynomial time algorithm for computing the description of the workspace boundary for the class of revolute jointed robot arms arising from polygonal orthogonal chains in 3D. Copyright 2011 ACM.

The problem of computing the maximum reach configurations of a 3D revolute-jointed manipulator is a long-standing open problem in robotics. In this paper we present an optimal algorithmic solution for orthogonal polygonal chains. This appears as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available, with no guarantee of obtaining the global maximum. In fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. We present elementary and efficient (mostly linear) algorithms for four fundamental problems: (1) finding the maximum reach value, (2) finding a maximum reach configuration (or enumerating all of them), (3) folding a given chain to a given maximum position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. The algorithms rely on our recent theoretical results characterizing combinatorially the maximum of panel-and-hinge chains. They allow us to reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar carpenter's rule problem.

We prove that the set of directions of lines intersecting three disjoint balls in R3 in a given order is a strictly convex subset of S2. We then generalize this result to n disjoint balls in Rd. As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.

(MATH) Rigid 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 first the number of distinct planar embeddings of rigid graphs with n vertices. We show that, modulo planar rigid motions, this number is at most $2n-4\choose n-2 \approx 4n. We also exhibit several families which realize lower bounds of the order of 2n, 2.21n and 2.88n.(MATH) For the upper bound we use techniques from complex algebraic geometry, based on the (projective) Cayley-Menger variety CM 2,n(C)\subset P_n\choose 2-1(C)$ over the complex numbers C. In this context, point configurations are represented by coordinates given by squared distances between all pairs of points. Sectioning the variety with 2n-4 hyperplanes yields at most deg(CM 2,n) zero-dimensional components, and one finds this degree to be D 2,n =\frac122n-4\choose n-2$. The lower bounds are related to inductive constructions of minimally rigid graphs via Henneberg sequences.(MATH) The same approach works in higher dimensions. In particular we show that it leads to an upper bound of 2 D^3,n= \frac2^n-3n-2n-6\choosen-3$ for the number of spatial embeddings with generic edge lengths of the $1$-skeleton of a simplicial polyhedron, up to rigid motions.