TY - GEN

T1 - Geodesic-preserving polygon simplification

AU - Aichholzer, Oswin

AU - Hackl, Thomas

AU - Korman, Matias

AU - Pilz, Alexander

AU - Vogtenhuber, Birgit

N1 - Funding Information:
Research supported by the ESF EUROCORES programme EuroGIGA - ComPoSe, Austrian Science Fund (FWF): I 648-N18 and grant EUI-EURC-2011-4306. T.H. supported by the Austrian Science Fund (FWF): P23629-N18 ‘Combinatorial Problems on Geometric Graphs’. M.K. received support of the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union. A.P. is recipient of a DOC-fellowship of the Austrian Academy of Sciences at the Institute for Software Technology, Graz University of Technology, Austria.

PY - 2013

Y1 - 2013

N2 - 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 P by a polygon P′ such that (1) P′, contains P, (2) P′, has its reflex vertices at the same positions as P, and (3) the number of vertices of 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 P and 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 P.

AB - 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 P by a polygon P′ such that (1) P′, contains P, (2) P′, has its reflex vertices at the same positions as P, and (3) the number of vertices of 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 P and 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 P.

UR - http://www.scopus.com/inward/record.url?scp=84893355167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893355167&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45030-3_2

DO - 10.1007/978-3-642-45030-3_2

M3 - Conference contribution

AN - SCOPUS:84893355167

SN - 9783642450297

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 11

EP - 21

BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings

T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013

Y2 - 16 December 2013 through 18 December 2013

ER -