Re: Re: Searching for a function

*To*: mathgroup at smc.vnet.net*Subject*: [mg70903] Re: [mg70872] Re: Searching for a function*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 1 Nov 2006 03:55:29 -0500 (EST)*References*: <ehv8vp$g6f$1@smc.vnet.net> <200610301033.FAA13379@smc.vnet.net> <45461632.5010501@wolfram.com> <099301c6fc37$113ae0f0$1e0110ac@bblaptop>

Bonny Banerjee wrote: > Thanks Daniel. My problem is: Given two paths and a set of obstacles, > find out whether the two paths are homotopic or not. If they are, what > is the homotopy function? > > Your algorithm only answers whether two paths are homotopic or not. It > does not provide any homotopy function in case they are homotopic. An > example of such a function is: > > F(u,t) = u*Path2(t) + (1-u)*Path1(t), where 0<=t<=1 and 0<=u<=1 > > There exists some value of u and t for which F(u,t) belongs to the set > of obstacles P. This proves that this particular function F is not a > homotopy function between Path1 and Path2. Or in other words, Path1 and > Path2 are not homotopic under the function F. But that does not > necessarily prove Path1, path2 are not homotopic. > > In case, Path1 and Path2 were homotopic, how do I figure out the > homotopy function? Is there a systematic way of choosing the homotopy > function? Or in other words, what properties of the paths and/or > obstacles determine the homotopy function? > > Any help will be appreciated. > > Thanks, > Bonny. > [See bottom. --DL] > ----- Original Message ----- > From: "Daniel Lichtblau" <danl at wolfram.com <mailto:danl at wolfram.com>> To: mathgroup at smc.vnet.net > Subject: [mg70903] Re: [mg70872] Re: Searching for a function > > > Bonny Banerjee wrote: > >> I was looking at the problem of finding whether two paths are > homotopic or > >> not. A path in 2D space (R^2) is a continuous mapping > Path:[0,1]->R^2, where > >> Path(0) and Path(1) are the two terminal points. Two paths, Path1 > and Path2, > >> are said to be homotopic with respect to a set of obstacles P if > they share > >> the same starting and ending points and one can be continuously > deformed > >> into the other without crossing any obstacle. Formally, Path1 and > Path2 are > >> homotopic to each other if there exists a continuous function > >> F:[0,1]*[0,1]->R^2 such that > >> > >> 1. F(0,t) = Path1(t) and F(1,t) = Path2(t), 0<=t<=1 > >> 2. F(u,0) = Path1(0) = Path2(0) and F(u,1) = Path1(1) = Path2(1), > 0<=u<=1 > >> 3. F(u,t) does not belong to P, 0<=u<=1 and 0<=t<=1 > >> > >> The problem: I have two paths, Path1 and Path2, which are finite > curves that > >> start at some point and end at another point. The domain is > piecewise linear > >> i.e. a path is a sequence of linear segments. I also have a set of > obstacle > >> points P. How do I compute, using Mathematica, whether these two > paths are > >> homotopic or not? > >> > >> Here is an example: > >> > >> Path1 is the sequence of points {(0,0), (10,0), (10,10)}. Thus, > >> Path1(t) = (20t, 0) for 0<=t<=1/2 > >> Path1(t) = (10, 20t-10) for 1/2<=t<=1 > >> > >> Path2 is the sequence of points {(0,0), (0,10), (2,12), (5,20), > (10,10)}. > >> Thus, > >> Path2(t) = (0, 40t) for 0<=t<=1/4 > >> Path2(t) = (8t-2, 8t+8) for 1/4<=t<=1/2 > >> Path2(t) = (12t-4, 32t-4) for 1/2<=t<=3/4 > >> Path2(t) = (20t-10, 50-40t) for 3/4<=t<=1 > >> > >> The obstacles are the set of points P = {(5,5), (7,5), (7,10), (5,10), > >> (12,12), (15,12), (15,20), (12,20)}. > >> > >> In this example, Path1 and Path2 are not homotopic because the > obstacles > >> {(5,5), (7,5), (7,10), (5,10)} have to be crossed in order for one > to be > >> deformed into the other. Thus, there does not exist any function F that > >> satisfies all the conditions for this example. > >> > >> Given two paths and a set of obstacles, how can I use Mathematica to > compute > >> whether there exists any function F or not? > >> > >> Thanks, > >> Bonny. > >> > > > > Your two paths define a region enclosed by linear segments. One approach > > to the question at hand would be to decide whether any of the given > > points are in the interior of that region. > > > > There are threads on MathGroup from September, 2000 that discuss this > > issue of determining whether a point is enclosed in a polygon. Check for > > subjects "Winding Number" and "Point inside a plygon?". Offhand I do not > > recall for certain if they handle the nonconvex case but I think they do. > > > > > > Daniel Lichtblau > > Wolfram Research Let's say you have checked and the obstruction points are not inside the polygon enclosed by the two paths. I don't really know how to obtain a homotopy between the paths but here are some possible approaches. If the polygon is convex then the "obvious" linear homotopy is just fine. If not then you can still use this provided that, if it goes outside the polygon, it still does not hit obstructions. So the problem, I think is to do one of the following things. (1) Keep the homotopy inside the polygon. (2) If you let it outside, keep it away from the obstruction points. I do not know how to attempt either using exact methods. For (1) you might try a variant of Sethian's "Level Set" methods based on curvature, except you'd not allow "outward" motion and you'd need to figure out how to keep endpoints fixed. As you restrict to only one direction it could even be done with "Fast Marching" (also due to Sethian and coauthors) which is more efficient. Keeping endpoints fixed might be done by having a "fix-up" step wherein as you go from F(u,t) to F(u+du,t) you first allow the endpoints to move, then stretch back the path to restore them. Offhand I do not know how easy this would be. Another possibility for maintaining endpoints may be to modify curvature continuously based on how far you are from the endpoints along either base path. You'd want it to be zero at endpoints so that no movement happens there. The important thing is to not allow F(u,t) for fixed t ever to "split" into disconnected subintervals. I'm not sure whether the general tactic I advocate will avoid this, though I think it might. For (2) you might try modifying the linear homotopy so that it avoids obstruction points, by placing a large potential in a small neighborhood of each as a sort of "penalty term". Offhand I don't know exactly how this would be done, but something like: F(u,t) = u*Path2(t) + (1-u)*Path1(t) + sum of penalties times gradients where the gradients go "outward" from small circles centered at the obstructions, and penalties are zero outside the small circles, and rise quickly inside them. But unless calibrated carefully, this would become an iterated computation at each step because a penalty from one obstruction could push you too close to another that you'd otherwsise not be near. Daniel Lichtblau Wolfram Research