Re: Searching for a function

*To*: mathgroup at smc.vnet.net*Subject*: [mg70872] Re: Searching for a function*From*: "Bonny Banerjee" <banerjee.28 at osu.edu>*Date*: Mon, 30 Oct 2006 05:33:05 -0500 (EST)*Organization*: Ohio State University*References*: <ehv8vp$g6f$1@smc.vnet.net>

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.