A triangulation is a decomposition of a polytope into finitely-many simplices (triangles in two dimensions, tetrahedra in three dimensions, d-dimensional simplices in a d-dimensional space) that intersect along common faces. Flips are local transformation that can be used to change a triangulation into another triangulation of the same polytope. Prescribing a finite set X of points then gives rise to a finite set of triangulations of the convex hull of X whose vertex set is a subset of X, which are for short, the triangulations of X. In turn, one can consider the flip-graph F(X) of X whose vertices are the triangulations of X and whose edges link two triangulations that can be obtained from one another by a flip. In two dimensions, the simplest flip consists in exchanging the diagonals the convex quadrilateral formed by two adjacent triangles. The figure on the right shows a sequence of flips in the plane.

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 finite set of points in the plane is connected. However, if X is a set of points in a euclidean space of dimension three or four, it is not known whether F(X) is connected in general. In dimension above four, sets of points are known whose flip-graph is disconnected [2,3,4].

A triangulation is regular when the simplices it is made of are projected from the boundary of some (d+1)-dimensional polytope. The subgraph R(X) induced in F(X) by regular triangulations is isomorphic to the edge-graph of the secondary polytope of X [5,6], and as a consequence it is connected. It turns out that this connectedness result can be strenghtened a little: if T and T' are two regular triangulations of X, it is possible to change T into T' by performing flips none of whose remove a face common to T and T' [7].

Triangulation regularity can be generalized as follows to higher codimensions: say a triangulation is k-regular when the simplices it is made of are projected from the boundary of a (d+k)-dimensional polytope and consider the subgraph R(X,k) induced in G(X) by k-regular triangulations. It turns out that R(X,2) is always connected and contains many examples of non-regular triangulations [8]. As an interesting example, Rudin's non-shellable (and therefore non-regular) triangulation [9] turns out to be 2-regular. This can be checked numerically and you will find here a code that allows to check that Rudin's triangulation is indeed 2-regular. When X is contained in the plane, all the triangulations of X are 2-regular or equivalently, R(X,2)=F(X) [10]. It is not known whether R(X,2) always coincides with F(X) when X is contained in a 3-dimensional space. If it were the case, this would show that F(X) is connected.