Geodesic-preserving polygon simplification

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Birgit Vogtenhuber

Research output: Contribution to journalArticlepeer-review


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
Original languageEnglish
Pages (from-to)307-323
JournalInternational Journal of Computational Geometry and Applications
Issue number4
Publication statusPublished - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Theoretical


Dive into the research topics of 'Geodesic-preserving polygon simplification'. Together they form a unique fingerprint.

Cite this