תקציר
We propose precise notions of what it means to guard a domain “robustly”, under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | 40th International Symposium on Computational Geometry, SoCG 2024 |
עורכים | Wolfgang Mulzer, Jeff M. Phillips |
מוציא לאור | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
מסת"ב (אלקטרוני) | 9783959773164 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - יוני 2024 |
אירוע | 40th International Symposium on Computational Geometry, SoCG 2024 - Athens, יוון משך הזמן: 11 יוני 2024 → 14 יוני 2024 |
סדרות פרסומים
שם | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
כרך | 293 |
ISSN (מודפס) | 1868-8969 |
כנס
כנס | 40th International Symposium on Computational Geometry, SoCG 2024 |
---|---|
מדינה/אזור | יוון |
עיר | Athens |
תקופה | 11/06/24 → 14/06/24 |
הערה ביבליוגרפית
Publisher Copyright:© Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell.