2013 | OriginalPaper | Buchkapitel
Geodesic-Preserving Polygon Simplification
verfasst von : Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Birgit Vogtenhuber
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is 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 polygon
$\mathcal{P}$
by a polygon
$\mathcal{P}'$
such that (1)
$\mathcal{P}'$
contains
$\mathcal{P}$
, (2)
$\mathcal{P}'$
has its reflex vertices at the same positions as
$\mathcal{P}$
, and (3) the number of vertices of
$\mathcal{P}'$
is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both
$\mathcal{P}$
and
$\mathcal{P}'$
, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of
$\mathcal{P}$
.