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.
Related notions to the geodesic width include the isotopic Fr ' e chet distance @cite_14 and the minimum deformation area @cite_7 between two curves @math and @math . Whereas the geodesic width considers deformations between @math and @math such that no two intermediate curves intersect, this restriction is not present for the isotopic Fr ' e chet distance, which can therefore be defined between intersecting curves. The paper @cite_7 considers a distance between two curves on a 2-manifold which is instead an area: the minimal total surface area swept out by any deformation between the two curves. If the curves are piecewise linear in the plane, have @math total vertices, and have @math intersection points, then @cite_7 gives an @math algorithm to compute the minimum deformation area between them.
@cite_14 @cite_7
2188165015 1999272835
We present a variant of the Frechet distance (as well as geodesic and homotopic Frechet distance) which forces the motion between the input objects to fol- low an ambient isotopy. This provides a measure of how much you need to continuously deform one shape into another while maintaining topologically equiva- lently shapes throughout the deformation. Measuring the similarity of curves is a fundamental problem arising in many application fields. There has been considerable interest in several such measures, both in Euclidean space and in more general setting such as curves on Riemannian surfaces or curves in the plane minus a set of obstacles. However, so far, efficiently computable similarity measures for curves on general surfaces remain elusive. This paper aims at developing a natural curve similarity measure that can be easily extended and computed for curves on general orientable 2-manifolds. Specifically, we measure similarity between homotopic curves based on how hard it is to deform one curve into the other one continuously, and define this "hardness" as the minimum possible surface area swept by a homotopy between the curves. We consider cases where curves are embedded in the plane or on a triangulated orientable surface with genus @math , and we present efficient algorithms (which are either quadratic or near linear time, depending on the setting) for both cases.