Geometric and computational problems involving points and objects of various shapes are basic to the understanding of geometric modeling, computer graphics, the analysis and synthesis of mechanisms, robot manipulation, structural analysis, protein folding and granular materials, for example. What are the geometric principles that are relevant to understanding how configurations of linkages in the plane can be reconfigured? What are the basic geometric tools that can be applied to understand and analyze the area/volume of various arrangements and formulas for the union and intersections of circular disks in the plane or space? Recent advances have shown that there are some subtle and insightful ideas that can be brought to bear on these very basic problems that include packing and covering problems as extreme special cases.
Suppose a configuration of points in the plane or space is given. The distance between some (but not all) of the pairs of these points is fixed. Is there another corresponding configuration, other than congruent copies of the original configuration, of the points with corresponding distances the same? When this occurs, the configuration is called globally rigid. When the configuration is sufficiently generic, there is a reasonable algorithm to determine if it is globally rigid. This is of interest in protein folding, point location problems and structural stability, for example. It is proposed that this theory and corresponding algorithms can be used to provide structural information about the shapes of molecules as well as the stability of a wide variety of novel structures.
There were three main areas where there was significant progress, the Kneser-Poulsen Conjecture, global rigidity questions, and jammed packings. The Kneser-Poulsen Conjecture says that if any finite configuration of spherical balls in Euclidean space is rearranged such that each pair of centers does not get closer together, an expansion of the centers, then the volume of the union of the balls does not decrease. By a result of the PI and K. Bezdek, this conjecture was proved for the plane, but it is open for all higher dimensions. Igors Gorbovickis, a student of the PI, showed that for a given expansion of a finite number of points, if the radii of disks, for those points as centers, is large enough, then the Kneser-Poulsen Conjecture holds. Gorbovickis also showed for any finite configuration of balls in dimension d, if the initial configuration of each ball intersects no more than d+2 other balls, then any expansion will not decrease the volume of their union. These results have been submitted and the first will appear. The Kneser-Poulsen problem seems to be quite difficult and, for the time being, we must settle for what information we can. Consider a finite collection of points in Euclidean space where some pairs are constrained to be at a fixed distance apart. If there is no other non-congruent configuration that satisfies those constraints, the structure is called a globally rigid framework. The PI has a matrix criterion that will determine whether a configuration, that is generic (which means that there is no non-zero integer polynomial relation among the coordinates of the configuration), is globally rigid. In the plane, B. Jackson and T. Jordan have shown, using this matrix criterion, that there is a polynomial time deterministic combinatorial algorithm that calculates the generic global rigidity in terms of the graph of the framework. In higher dimensions, in general, there does not seem to be such an algorithm, even for local generic rigidity. For the case when the framework is given by globally rigid subframeworks, called bodies, T. Jordan, W. Whiteley, and the PI have shown that, for such generic bar-body frameworks, there is again a deterministic, polynomial-time algorithm that calculates generic global rigidity. The algorithm is simple, but the proof is tricky. Another way to create generic globally rigid frameworks is to create them inductively. There are easy methods by combining pairs of globally rigid frameworks with large common sub-frameworks, for example, but this can create a large number of extraneous bars. The PI has shown that if the intersection of two globally rigid frameworks in dimension d has exactly d + 1 vertices, then any one common bar of the two frameworks can be eliminated and the resulting framework will be globally rigid, again in d-space. This will appear in the Proceedings of the Russian Academy of Sciences. A collection of disks in a container is called a packing if their interiors do not overlap. Such a packing is said to be jammed, if it has no nontrivial motions preserving the packing condition. It is important for granular materials, codes, and number theory to find dense or locally maximally dense configurations of disks in various containers. Locally maximally dense packings tend to be jammed, possibly with a few rattlers rattling around. One particularly interesting container is a fixed flat torus, even in the case of the plane. Such packings correspond to infinite periodic packings determined by a fixed lattice, and a particularly interesting lattice is the one determined by two unit vectors 60 degrees apart, the ubiquitous triangular lattice. The problem is to determine the most dense packing of n equal disks in a torus given by such a lattice. If n is of the the form a^2 +ab + b^2, for a and b integers, called a triangular lattice number, then there is another triangular sublattice of the given triangular lattice that corresponds to a packing of n disks, that is well-known to be of maximal density. When n is not a triangular lattice number, any packing of n disks in the triangular torus must have a lower density. The PI has conjectured that when n is not a triangular lattice number, but n +1 is, then the most dense packing of n disks in a triangular torus can only be given by removing one disk from the densest packing of n+1 disks. The PI has shown that there are several cases when the packing is jammed and this upper bound on the packing density holds. This paper is submitted to the Proceeding of the Russian Academy of Sciences.
