A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points

摘要

We describe a simple algorithm to triangulate a special class of 3d non-convex polyhedra without Steiner points (vertices which are not the vertices of the given polyhedron). We prove sufficient conditions for the termination of this algorithm, and show that it runs in O(n~3) time, where n is the number of input vertices.