MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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. 



  • Prev by Date: Re: Re: Searching for a function
  • Next by Date: Re: Re: Searching for a function
  • Previous by thread: Re: Searching for a function
  • Next by thread: Singularity handling in NIntegrate