Let D be a Jordan domain in the plane. We consider a pursuit-evasion, contamination clearing, or sensor sweep problem in which the pursuer at each point in time is modeled by a continuous curve, called the sensor curve. Both time and space are continuous, and the intruders are invisible to the pursuer. Given D, what is the shortest length of a sensor curve necessary to provide a sweep of domain D, so that no continuously-moving intruder in D can avoid being hit by the curve? We define this length to be the sweeping cost of D. We provide an analytic formula for the sweeping cost of any Jordan domain in terms of the geodesic Frechet distance between two curves on the boundary of D with non-equal winding numbers. As a consequence, we show that the sweeping cost of any convex domain is equal to its width, and that a convex domain of unit area with maximal sweeping cost is the equilateral triangle.
The paper @cite_2 introduces the between two polylines, a notion that is very relevant for our problem. The geodesic width between two curves @math , @math is the same as the strong geodesic Fr ' e chet distance between them (Definition ) when domain @math is chosen to be a region with boundary consisting of curves @math , @math , and the two shortest paths connecting the endpoints of @math and @math . If curves @math and @math are polylines with @math vertices in total, then @cite_2 gives an @math algorithm for computing the geodesic width between them. The goal of our paper is instead to rigorously prove an analytic formula for the sweeping cost of a domain, Theorem , that is closely related to geodesic widths. Indeed, the right hand side of in Theorem is unchanged if we replace the geodesic distance between two curves (Definition ) with the weak geodesic Fr ' e chet distance between them (Definition ). The paper @cite_2 also studies sweeps of planar domains by piecewise linear curves in which the cost of a sweep is not equal to a length, but instead to the number of vertices or joints in the curve.
@cite_2
2062556295
We introduce two new related metrics, the geodesic width and the link width, for measuring the "distance" between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n 2 log n) time using O(n 2) space and the link width in O(n 3 log n) time using O(n 2) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: