# A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon

Stav Ashur, Omrit Filtser, Matthew J. Katz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

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 + ε) -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 + ε) -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. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygon’s boundary. Finally, our algorithms may become useful as part of the grand attempt of Bhattacharya et al. to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.

اللغة الأصلية الإنجليزيّة Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers Christos Kaklamanis, Asaf Levin Springer Science and Business Media Deutschland GmbH 81-96 16 9783030808785 https://doi.org/10.1007/978-3-030-80879-2_6 نُشِر - 2021 نعم 18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Onlineالمدة: ٩ سبتمبر ٢٠٢٠ → ١٠ سبتمبر ٢٠٢٠

### سلسلة المنشورات

الاسم Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12806 LNCS 0302-9743 1611-3349

### !!Conference

!!Conference 18th International Workshop on Approximation and Online Algorithms, WAOA 2019 Virtual, Online ٩/٠٩/٢٠ → ١٠/٠٩/٢٠

### ملاحظة ببليوغرافية

Funding Information:
Keywords: Geometric optimization · Approximation algorithms · Visibility · Art gallery problems O. Filtser was supported by the Eric and Wendy Schmidt Fund for Strategic Innovation, by the Council for Higher Education of Israel, and by Ben-Gurion University of the Negev. M. Katz was supported by grant 1884/16 from the Israel Science Foundation.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

## بصمة

أدرس بدقة موضوعات البحث “A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon'. فهما يشكلان معًا بصمة فريدة.