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 2162114735 2062556295 2407537893
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. We present a heuristic algorithm to compute approximate geodesic distances on a triangular manifold S containing n vertices with partially missing data. The proposed method computes an approximation of the geodesic distance between two vertices pi and pj on S and provides an upper bound of the geodesic distance that is shown to be optimal in the worst case. This yields a relative error bound of the estimate that is worst-case optimal. The algorithm approximates the geodesic distance without trying to reconstruct the missing data by embedding the surface in a low dimensional space via multi-dimensional scaling (MDS). We derive a new heuristic method to add an object to the embedding computed via least-squares MDS. 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: Given a polygon @math , for two points @math and @math contained in the polygon, their is the length of the shortest @math -path within @math . A of radius @math centered at a point @math is the set of points in @math whose geodesic distance to @math is at most @math . We present a polynomial time @math -approximation algorithm for finding a densest geodesic unit disk packing in @math . Allowing arbitrary radii but constraining the number of disks to be @math , we present a @math -approximation algorithm for finding a packing in @math with @math geodesic disks whose minimum radius is maximized. We then turn our focus on of @math and present a @math -approximation algorithm for covering @math with @math geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are @math -hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius.