Optimizing Visibility-based Search in Polygonal Domains
<|reference_start|>Optimizing Visibility-based Search in Polygonal Domains: Given a geometric domain $P$, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within $P$ in order to be able to see a portion (or all) of $P$, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within $P$ according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of $P$. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain $P$ in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of $P$ (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon $P$ we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains $P$ (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in $P$ to guarantee some specified probability of detection of a static target within $P$, randomly distributed in $P$ according to a given prior distribution.<|reference_end|>
@article{huynh2024optimizing,
    title={Optimizing Visibility-based Search in Polygonal Domains},
    author={Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, Valentin Polishchuk},
    journal={19th Scandinavian Symposium on Algorithm Theory, SWAT 2024},
    year={2024},
    doi={10.4230/LIPIcs.SWAT.2024.27},
    archivePrefix={arXiv},
    eprint={2402.05420},
    primaryClass={cs.CG}
}