Demonstrates necessary operations for triangulating polygons with holes, suggesting algorithmic efficiency in partitioning.
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.
No takes yet. Share an insight, caveat, or question.
Asano et al. (1986) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: