Search for: All records

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. 

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. 

Let {\$$}{\$$}E={\backslash}{\{}e{\_}1,{\backslash}ldots ,e{\_}n{\backslash}{\}}{\$$}{\$$}be a set of C-oriented disjoint segments in the plane, where C is a given finite set of orientations that spans the plane, and let s and t be two points. We seek a minimum-link C-oriented tour of E, that is, a polygonal path {\$$}{\$$}{\backslash}pi {\$$}{\$$}from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in {\$$}{\$$}O(|C|^2 {\backslash}cdot n^2){\$$}{\$$}time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.