Discrete geometry and topology in low dimensions (07w5111)
Karoly Bezdek (University of Calgary)
Robert Connelly (Cornell University)
Herbert Edelsbrunner (Institute of Science and Technology (Austria))
Voronoi cells and their applications
Voronoi cells are widely used in mathematics as well as in many areas of science. Voronoi cells and tilings can be applied to quite a number of problems and this character of them is a result of the large list of impressive combinatorial, geometric as well as topologic properties known today. This part of our proposed workshop will focus on some of the most challenging issues that are still open and have the potential to influence significantly any further research progress on Voronoi cells and their applications. Also, the list below is internally connected to the other two major components of our meeting.
(1) One of the best known conjectures of discrete geometry was raised by Voronoi in 1908. Voronoi conjectured that any parallelotope is an affine image of the Voronoi cell of some lattice. There has been a great deal of work done on this conjecture. Delaunay (1929) proved Voronoi’s conjecture for dimensions up to 4. Just recently Engel (2000) proved it for 5-dimensional parallelotopes. Due to several highly nontrivial partial results one can hope for significant progress on this conjecture in the near future. Our meeting should discuss the state of the art of the problem in full details.
(2) Poulsen (1954) and Kneser (1955) independently conjectured that if a finite set of d-dimensional balls in Euclidean d-space is rearranged so that the distance between each pair of centers does not decrease, then the volume of union of the balls does not decrease. This is a very important fundamental problem. Just recently the planar case of the Kneser-Poulsen conjecture has been proved by Bezdek and Connelly (2002) based on methods built on Voronoi cells associated with the center points of the balls. The method used strongly suggest to investigate the behavior of the volume, surface area etc. of unions of balls (resp., Voronoi cells) under contractions of their center points. Our meeting should give a better understanding of the nature of the difficulties involved.
(3) The celebrated proof of the Kepler conjecture by Hales (1998-2004) as well as the proof of the dodecahedral conjecture by Hales and McLaughlin (1998-2004) calls the attention to the isoperimetric type problems of individual Voronoi cells. In fact, these questions are connected to the still widely open problem of Kelvin (1887) on tiling the space into equal volume pieces with smallest possible average surface area. This question arises naturally in the theory of foams when the liquid content is small. Kelvin proposed that the solution was a 14-sided truncated octahedron having a very slight curvature of the hexagonal faces. Despite one hundred years of failed attempts and Weyl's (1952) opinion that the curved truncated octahedron could not be improved upon, Weaire and Phelan (1994) discovered a space-filling unit cell consisting of six 14-sided polyhedra and two 12-sided polyhedra with irregular faces and only hexagonal faces remaining planar. This structure has an isoperimetric quotient of 0.764, or approximately 0.3 percent less that Kelvin's cell. Somewhat surprisingly there is underlying Voronoi tiling in the construction of Weaire and Phelan. The question of looking for further progress using Voronoi tilings seems to be natural one and should be discussed at our meeting.
Distance geometry and volume calculations
One of the most basic aspects of discrete geometry has to do with the distance between points and how these distances effect the volume of objects they define. For example, the Kneser-Poulsen Conjecture mentioned in the “Voronoi cells and their applications” section is a very basic question that relates the distances between the centers of disks to the volume of their union or intersection. In the proof of the Kneser-Poulsen Conjecture in the plane by Bezdek and Connelly, the only part that prevents it from being extended to three-dimensional Euclidean space is a distance geometry question about configurations of points. If one configuration is a contraction of another in three-space, can the contraction be achieved continuously and monotonically in five-dimensional Euclidean space? There is also a very intriguing question whether a contraction in the hyperbolic plane can be achieved continuously and monotonically in four-dimensional hyperbolic space.
Another very good problem is the calculation of the volume bounded by an oriented surface in Euclidean space. In 1977, Connelly showed that there are embedded triangulated spheres in Euclidean three-space that are perfect mechanisms. In other words, there is a continuous non-congruent motion of the vertices such that all the edges have fixed length. Then in 1995, Sabitov showed that the volume bounded by such a flexible surface is constant during the motion. This was done by showing that there is a polynomial, whose coefficients are themselves polynomials in the squares of the edge lengths, that is satisfied by the volume bounded by the surface. This is a property of volumes that is deeper and more subtle than simply taking integrals. Recently, related volume and area formulas have been found by finding similar polynomials relating the area bounded by a planar polygon with its vertices on a circle, in response to a problem promoted by David Robinson. But there remain several questions about the possibility of similar polynomials even for four-dimensional Euclidean space, as well as possible geometric interpretations of the coefficients of these polynomials.
Persistent topology and witness complexes
Voronoi diagrams and their dual Delaunay triangulations form an important class of complexes that can be used to model shapes, among other applications. Subcomplexes of the Delaunay triangulation also
arise as inclusion-exclusion formulas for the volume of a union of balls. Specifically, Edelsbrunner proved in 1995 that the alpha complex gives a correct inclusion-exclusion formula, and Attali and Edelsbrunner in 2004 generalized this result by identifying a class of minimal inclusion-exclusion formulas.
We are interested in using these and other complexes to study experimentally obtained datasets, in particular large point clouds in possibly high-dimensional space. For a given dataset, we may form a
filtration (a nested sequence of complexes) to express its multi-scale shape properties. An example is the family of alpha shapes which furnishes a multi-scale view of protein structures, for instance. In
2000, Edelsbrunner, Letscher and Zomorodian introduced the concept of persistent homology, which arises because a homology class may live through a short or a long subsequence of the filtration. In 2004, Cohen-Steiner, Edelsbrunner and Harer showed that persistence is stable under perturbations, which opened up the gates for a number of developments, including proofs for homology inference, methods for shape comparison, curve diagrams for time-varying functions, new inequalities for curvature, etc. A major open question in this field is how to generalize the concept of persistence to two- and more-parametric filtrations.
An interesting parallel development started in 2004 with the work of de Silva and Carlsson who introduced witness complexes as a generalization of the topology adapting networks defined in 1994 by Martinetz and Schulten. Their main motivation is the determination of the gross topology of a point cloud. There are many open questions motivated by computational considerations, such as whether there are classes of small complexes capturing the same or the essential information, similar to the alpha shapes capturing the homotopy type of the generally much larger Cech complexes.
Discrete geometry is very "alive and visible", for example let us mention three recent international events.
(a) There was a special semester including the topics of our proposed workshop at the Mathematical Sciences Research Institute, Berkeley, California, in 2003, “Discrete and Computational Geometry.”
(b) There was a workshop at the Mathematisches Forschungsinstitut Oberwolfach, Germany, in April 2005, “Workshop on Discrete Geometry.”
(c) There is an ongoing European Union project based at the Renyi Institute, Budapest, Hungary that started in 2005, entitled “DiscConvGeo - Discrete and Convex Geometry.”
Last but not least we mention that our proposal was motivated by the very successfull 5-day BIRS meeting on "Densest Sphere Packings" (May 15-19, 2005; organizers: K. Bezdek, H. Cohn and C. Radin) and can be regarded as an extension of the topics discussed there.