Publication
Journal of Algorithms
Paper

Polygon triangulation: Efficiency and minimality

View publication

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.

Date

01 Jan 1986

Publication

Journal of Algorithms

Authors

Share