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.