2026-08-12T09:19:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24270 2025-11-12T13:39:41Z ddc:004 open_access

Sweeping a Domain with Line-Of-Sight Between Covisible Agents Huynh, Kien C. Mitchell, Joseph S. B. Polishchuk, Valentin Polygon sweeping collaborating agents motion coordination makespan optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kien C. Huynh and Joseph S. B. Mitchell and Valentin Polishchuk 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.39 urn:nbn:de:0030-drops-242706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.39 eng https://creativecommons.org/licenses/by/4.0/legalcode