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

Abstract

This paper studied the geometric and combinatorial aspects of the classical Lawsons flip algorithm [21, 22]. Let A be a finite point set in R2 and : A R be a height function which lifts the vertices of A into R3. 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 R3. 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 Lawsons algorithm works and why it may fail in general. We further characterised the triangulations which cause failure of Lawsons 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(n3) time, where n is the number of input vertices.