Polygon triangulation: Efficiency and minimality

Abstract

In this paper we show that Ω(n log n) operations are necessary to triangulate a polygonal region with n vertices which contains holes (or windows). Also, we present a polynomial time algorithm for partitioning a polygonal region which may have a fixed number of holes into a minimum number of triangles. Finally, we discuss arbitrary-as opposed to chordal-minimum-number triangulations. © 1986.