Geodesic-preserving polygon simplification

DOI10.1142/S0218195914600097MaRDI QIDQ5261017zbMATH OpenFDO

Authors Oswin Aichholzer, Alexander Pilz, Birgit Vogtenhuber, T. Hackl, Matias Korman

Publication date 1 July 2015

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.3858

zbMATH Keywords

geodesicshortest pathVoronoi diagrampolygonpolygonal domainsimple polygongeodesic hull

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 $mathcalP$ by a polygon $mathcal{P}^{\prime }$ such that (1) $mathcal{P}^{\prime }$ contains $mathcalP$, (2) $mathcal{P}^{\prime }$ has its reflex vertices at the same positions as $mathcalP$, and (3) the number of vertices of $mathcal{P}^{\prime }$ 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 $mathcalP$ and $mathcal{P}^{\prime }$, 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 $mathcalP$.

Recommendations

• Geodesic-preserving polygon simplification
• Simplifying a polygonal subdivision while keeping it simple
• Progressive simplification of polygonal curves

Cites work

• A generalized Winternitz theorem
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Computing minimum length paths of a given homotopy class
• Constructing pairwise disjoint paths with few links
• Extreme point and halving edge search in abstract order types
• Geodesic order types
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Minimum-link paths revisited
• On minimum-area hulls
• On-line construction of the convex hull of a simple polyline
• Optimal shortest path queries in a simple polygon
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• The furthest-site geodesic Voronoi diagram
• Triangulating a simple polygon in linear time
• Triangulations, visibility graph and reflex vertices of a simple polygon
• \(L_ 1\) shortest paths among polygonal obstacles in the plane

Cited in

(8)

• scientific article; zbMATH DE number 98471 (Why is no real title available?)
• Piercing pairwise intersecting geodesic disks
• On simplifying shapes by subjecting them to collinearity constraints
• Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• Geodesic-preserving polygon simplification
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

This page was built for publication: Geodesic-preserving polygon simplification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261017)