WIAS Preprint No. 2554, (2018)

On monotone sequences of directed flips, triangulations of polyhedra, and structural properties of a directed flip graph


  • Si, Hang

2010 Mathematics Subject Classification

  • 65D18 68U05 65M50


  • weighted Delaunay triangulations, non-regular triangulations, Lawson's flip algorithm, directed flips, monotone sequence, flip graph, Higher Stasheff-Tamari poset, redundant interior vertices, Schönhardt polyhedron, Steiner points




This paper studied the geometric and combinatorial aspects of the classical Lawson's flip algorithm  [21, 22]. Let A be a finite point set in R^2 and ω : A → R be a height function which lifts the vertices of A into R^3. Every flip in triangulations of A can be assigned a direction [6, Definition 6.1.1]. A sequence of directed flips is monotone if all its flips follow the same direction. We first established a relatively obvious relation between monotone sequences of directed flips on triangulations of A and triangulations of the lifted point set A^ω in R^3. We then studied the structural properties of a directed flip graph (a poset) on the set of all triangulations of A. We proved several general properties of this poset which clearly explain when Lawson's algorithm works and why it may fail in general. We further characterised the triangulations which cause failure of Lawson's algorithm, and showed that they must contain redundant interior vertices which are not removable by directed flips. A special case of this result in 3d has been shown in [19]. As an application, we described a simple algorithm to triangulate a special class of 3d non-convex polyhedra without using additional vertices. We prove sufficient conditions for the termination of this algorithm, and show it runs in O(n^3) time, where $n$ is the number of input vertices.

Download Documents