A new triangulation-linear class of simple polygons

Publisher Website
Google Scholar
Abstract
A new polygon class taking linear-time and space for triangulation, called an if-polygon, is defined. After describing an algorithm for triangulating this class, we show that some triangulation-linear classes previously known, such as a convex polygon, a spiral polygon, an edge-visible polygon and a chain-visible polygon have the same property, called the if-property, as the newly defined class. Consequently, a monotone-separable polygon and a star-shaped polygon can be considered as a union of two if-polygons, respectively. Also, we present a modified algorithm for triangulating a star-shaped polygon without decomposition. As a result, the algorithm is simpler to implement and easier to understand and its correctness can be easily verified.

This publication has 8 references indexed in Scilit: