A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
| Autor: | Stav Ashur, Matthew J. Katz, Omrit Filtser |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Conjecture
Approximation algorithm Boundary (topology) Field (mathematics) Computer Science::Computational Geometry Computational geometry Vertex (geometry) Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Polygon Simple polygon ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Approximation and Online Algorithms ISBN: 9783030808785 WAOA |
| DOI: | 10.1007/978-3-030-80879-2_6 |
| Popis: | The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time \(O(\log n)\)-approximation algorithm for placing as few guards as possible at vertices of a simple n-gon P, such that every point in P is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a \((2+{\varepsilon })\)-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon P is weakly visible if it has an edge e, such that every point in P is visible from some point on e. We also present a \((2+{\varepsilon })\)-approximation algorithm for guarding a weakly visible polygon P, where guards may be placed anywhere on P’s boundary (except in the interior of the edge e). Finally, we present an O(1)-approximation algorithm for vertex guarding a polygon P that is weakly visible from a chord. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|