Triangulating Simple Polygons and Equivalent Problems

Publisher Website
Google Scholar
Abstract
It' has long been known that the complexity of triangulation of simple polygons having an upper bound of 0 (n log n) but a lower bound higher than ~(n) has not been proved yet. We propose here an easily implemented route to the triangulation of simple polygons through the trapezoidization of simple polygons, which is currently done in O(n log n). Then the trapezoidized polygons are triangulated in O(n) time. Both of those steps can be performed on polygons with holes with the same complexity. We also show in this paper that a number of problems, such as the decomposition of simple polygons into convex, star, monotone, spiral, and trapezoidal polygons and the determination of edgevertex visibility, are linearly equivalent to the triangulation problem and therefore share the same lower bound. It is hoped that this will simplify the task of reducing the gap between the lower and upper bound for these problems.

This publication has 10 references indexed in Scilit: