The existence of triangulations of non-convex polyhedra without new vertices

Abstract

It is well known that a simple three-dimensional non-convex polyhedron may not be triangulated without using new vertices (so-called it Steiner points). In this paper, we prove a condition that guarantees the existence of a triangulation of a non-convex polyhedron (of any dimension) without Steiner points. We briefly discuss algorithms for efficiently triangulating three-dimensional polyhedra.