Robustly Guarding Polygons

Rathish Das; Omrit Filtser; Matthew J. Katz; Joseph S.B. Mitchell

doi:10.4230/LIPIcs.SoCG.2024.47

Robustly Guarding Polygons

Rathish Das
, Omrit Filtser
, Matthew J. Katz
, Joseph S.B. Mitchell

מדעי המחשב

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

תקציר

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)	https://doi.org/10.4230/LIPIcs.SoCG.2024.47
סטטוס פרסום	פורסם - יוני 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.

גישה למסמך

10.4230/LIPIcs.SoCG.2024.47

קבצים וקישורים אחרים

Link to publication in Scopus

פורמט ציטוט ביבליוגרפי

Das, R., Filtser, O., Katz, M. J., & Mitchell, J. S. B. (2024). Robustly Guarding Polygons. ב- W. Mulzer, & J. M. Phillips (עורכים), 40th International Symposium on Computational Geometry, SoCG 2024 המאמר 47 (Leibniz International Proceedings in Informatics, LIPIcs; כרך 293). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2024.47

@inproceedings{8aba9ab4bddf46dfbfb786888902c38d,

title = "Robustly Guarding Polygons",

abstract = "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.",

keywords = "approximation algorithms, geometric optimization, guarding",

author = "Rathish Das and Omrit Filtser and Katz, \{Matthew J.\} and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell.; 40th International Symposium on Computational Geometry, SoCG 2024 ; Conference date: 11-06-2024 Through 14-06-2024",

year = "2024",

month = jun,

doi = "10.4230/LIPIcs.SoCG.2024.47",

language = "אנגלית",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Wolfgang Mulzer and Phillips, \{Jeff M.\}",

booktitle = "40th International Symposium on Computational Geometry, SoCG 2024",

address = "גרמניה",

}

Das, R, Filtser, O, Katz, MJ & Mitchell, JSB 2024, Robustly Guarding Polygons. ב- W Mulzer & JM Phillips (עורכים), 40th International Symposium on Computational Geometry, SoCG 2024., 47, Leibniz International Proceedings in Informatics, LIPIcs, כרך 293, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 40th International Symposium on Computational Geometry, SoCG 2024, Athens, יוון, 11/06/24. https://doi.org/10.4230/LIPIcs.SoCG.2024.47

Robustly Guarding Polygons. / Das, Rathish; Filtser, Omrit; Katz, Matthew J. et al.
40th International Symposium on Computational Geometry, SoCG 2024. עורך / Wolfgang Mulzer; Jeff M. Phillips. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. 47 (Leibniz International Proceedings in Informatics, LIPIcs; כרך 293).

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

TY - GEN

T1 - Robustly Guarding Polygons

AU - Das, Rathish

AU - Filtser, Omrit

AU - Katz, Matthew J.

AU - Mitchell, Joseph S.B.

PY - 2024/6

Y1 - 2024/6

N2 - 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.

AB - 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.

KW - approximation algorithms

KW - geometric optimization

KW - guarding

UR - https://www.scopus.com/pages/publications/85195453984

U2 - 10.4230/LIPIcs.SoCG.2024.47

DO - 10.4230/LIPIcs.SoCG.2024.47

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:85195453984

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 40th International Symposium on Computational Geometry, SoCG 2024

A2 - Mulzer, Wolfgang

A2 - Phillips, Jeff M.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 40th International Symposium on Computational Geometry, SoCG 2024

Y2 - 11 June 2024 through 14 June 2024

ER -

Robustly Guarding Polygons

תקציר

סדרות פרסומים

כנס

הערה ביבליוגרפית

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי