Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.