TY - GEN
T1 - Sweeping a Domain with Line-Of-Sight Between Covisible Agents
AU - Huynh, Kien C.
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
N1 - Publisher Copyright:
© Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk.
PY - 2025/8/29
Y1 - 2025/8/29
N2 - We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of “window partition” of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
AB - We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of “window partition” of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
KW - collaborating agents
KW - makespan optimization
KW - motion coordination
KW - Polygon sweeping
UR - https://www.scopus.com/pages/publications/105018742437
U2 - 10.4230/LIPIcs.WADS.2025.39
DO - 10.4230/LIPIcs.WADS.2025.39
M3 - Conference contribution
AN - SCOPUS:105018742437
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 19th International Symposium on Algorithms and Data Structures, WADS 2025
A2 - Morin, Pat
A2 - Oh, Eunjin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 19th International Symposium on Algorithms and Data Structures, WADS 2025
Y2 - 11 August 2025 through 15 August 2025
ER -