A sequence of flips that transforms triangulation T_{1} into triangulation T_{2}. Here, each flip replaces the dashed edge by the bold one.

*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 G_{1}(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 T_{1} and T_{2} are two regular triangulations of A, it is indeed possible to change T_{1} into T_{2} by only performing flips that do not remove any face common to T_{1} and T_{2} [7].

In 2009, I found a connected subgraph of G(A) that is much larger that G_{1}(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 G_{k}(A) induced in G(A) by k-regular triangulations. I proved in [8] that G_{2}(A) is connected. Nonetheless does G_{2}(A) contain G_{1}(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.

### [1]

**Software for C**^{1} interpolation

C. L. Lawson, in Mathematical Software III (J. Rice, ed.), pp. 161-194, Academic Press, New York (1977)

### [2]

### [3]

### [4]

### [5]

**Discriminants of polynomials of several variables and triangulations of Newton polyhedra**

I. M. Gel'fand, M. M. Kapranov, and A. V. Zelevinsky, Leningrad Math. J. **2**, 449-505 (1990)

### [6]

### [7]

### [8]

### [9]