On geodesic properties of polygons relevant to linear time triangulation (Q1118350)

The paper provides a contribution to the problem of finding optimal (linear time) algorithm for triangulating simple polygons. Two new classes of polygons, called palm polygons and crab polygons are introduced. The class of palm polygons contains many known classes of polygons for which linear time triangulation algorithms are known and a linear time algorithm for triangulating palm polygons is presented. The class of crab polygons is shown to contain all classes of polygons for which linear time triangulation algorithms are known up to now. However, the problem of linear time identification and triangulation of crab polygons remains open.