Delaunay triangulations are the main ingredient of the detection algorithm I use to perform granular media simulations. In general, a triangulation is a decomposition of a polytope into simplices (triangles in two dimensions and tetrahedra in three dimensions) that intersect along common faces. Weighted Delaunay (or regular) triangulations constitute a category of triangulations with nice regularity properties that provide an efficient contact detection method. In this algorithm, the vertices of the triangulation are attached to the particle. When the particles move, the geometry of the triangulation changes and the regularity properties have to be maintained using flips.
Flips are local transformation that can be used to change a triangulation of a set of points into another triangulation of this set of points. The flip-graph of such a set of points is the graph whose vertices are the triangulations, and whose edges link two triangulations that can be obtained from one another using a flip. In two dimensions, simplest flips consist in exchanging the diagonals a convex quadrilateral formed by two adjacent triangles. The figure on the right shows a sequence of such flips.
It is well-known that any two-dimensional triangulation can be changed into any other triangulation of the same set of points using flips [1]. In other words, the flip-graph of a two-dimensional set of points is connected. The problem remains open in the case of three- and four-dimensional triangulations, and has even been settled for the negative by Francisco Santos in dimensions above four [2,3,4]. The contact detection algorithm implemented in the simulation code I contributed to develop uses three-dimensional flips, and its convergence is theoretically conditioned to the connectedness of the flip-graph. I am therefore particularly interested in investigating this problem.
Consider a finite set of points A whose affine hull has dimension d, and denote by G(A) its flip-graph. A regular triangulation of A is a triangulation of A whose faces are projected from the boundary of a (d+1)-dimensional polytope. The subgraph G1(A) induced in G(A) by regular triangulations is isomorphic to the 1-skeleton of the secondary polytope [5,6], and as a consequence it is connected. It turns out that this connectedness result can be strenghtened a little: if T1 and T2 are two regular triangulations of A, it is indeed possible to change T1 into T2 by only performing flips that do not remove any face common to T1 and T2 [7].
In 2009, I found a connected subgraph of G(A) that is much larger that G1(A). In order to define this subgraph, I generalized the notion of regularity to higher codimensions: a triangulation of A is k-regular if it is projected from the boundary complex of a (d+k)-dimensional polytope. Now consider the subgraph Gk(A) induced in G(A) by k-regular triangulations. I proved in [8] that G2(A) is connected. Nonetheless does G2(A) contain G1(A) as a subgraph, it also contains many non-regular triangulations. One will find in [8] proofs that many of the known examples of non-regular triangulations are actually 2-regular. In particular, Rudin's non-shellable (hence non-regular) triangulation [9] turns out to be 2-regular. This can be checked numerically and you will find here the mathematica code I used to verify that the construction described in [8] indeed proves Rudin's triangulation 2-regularity.