2026-07-25T14:55:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20067 2024-05-31T13:11:11Z ddc:004 open_access

Optimizing Visibility-Based Search in Polygonal Domains Huynh, Kien C. Mitchell, Joseph S. B. Nguyen, Linh Polishchuk, Valentin Quota watchman route problem budgeted watchman route problem visibility-based search approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kien C. Huynh and Joseph S. B. Mitchell and Linh Nguyen and Valentin Polishchuk 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.27 urn:nbn:de:0030-drops-200671 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode