Geodesic-preserving polygon simplification

Polygons are a paramount data structure in computational geometry. While the com-plexity of many algorithms on simple polygons or polygons with holes depends on thesize of the input polygon, the intrinsic complexity of the problems these algorithms solveis often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygonPby a polygonP′such that(1)P′containsP, (2)P′has its reflex vertices at the same positions asP, and (3) thenumber of vertices ofP′is linear in the number of reflex vertices. Since the solutionsof numerous problems on polygons (including shortest paths, geodesic hulls, separatingpoint sets, and Voronoi diagrams) are equivalent for bothPandP′, our algorithm canbe used as a preprocessing step for several algorithms and makes their running tim