MathGroup Archive 2006

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

Search the Archive

Re: Re: Searching for a function

  • To: mathgroup at smc.vnet.net
  • Subject: [mg70874] Re: [mg70854] Re: Searching for a function
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Mon, 30 Oct 2006 05:33:07 -0500 (EST)
  • References: <ehv8vp$g6f$1@smc.vnet.net> <200610290340.XAA08628@smc.vnet.net> <0352689D-3226-4F4C-BE3C-8ED8F651C7D5@mimuw.edu.pl> <077d01c6fb9a$4337e5f0$1e0110ac@bblaptop>

This is a rather different prolem form the one you originally posted  
(or appeared to).  Actually, it amounts to the problem that has been  
frequently discussed on this list over the years: that of deciding if  
a point lies inside a polygon or not. Your two piecewise linear paths  
will define a polygon, and the paths will be homotopic in R^2 with  
your set of points removed if and only if none of the "obstacles"  
lies inside this polygon. There are many ways to decide if a point  
lies inside a polygon or not but I think the most efficient uses  
winding numbers. Such a code has been also posted several times; so I  
will just quote something that was posted in 2000 by William Self:

windingNumber[point_, vList_] := Module[
{g, ang},
g[t_] := Mod[t + Pi, 2Pi] - Pi;
ang[p_, a1_, a2_] := g[ArcTan @@ (a2 - p) - ArcTan @@ (a1 - p)];
(Plus @@ MapThread [ ang[point, #1, #2] & , {vList, RotateLeft[vList]}
])/2/Pi]

So, making use of that,  here is a function which will decide if two  
paths, described just as you have done, are homotopic in the plane  
with the obstacles removed:

homotopicQ[path1_, path2_, obstacles_] := With[{poly =
      poly = Join[path1, Most[Rest[
   Reverse[path2]]]]}, And @@ (Map[windingNumber[#,
             poly] &, obstacles] /. {0 -> True, _Integer -> False})]

For your example:


path1={{0,0},{10,0},{10,10}};path2={{0,0},{0,10},{2,12},{5,20},{10,10}};
obstacles={{5,5},{7,5},{7,10},{5,10},{12,12},{15,12},{15,20},{12,20}};


homotopicQ[path1,path2,obstacles]

False


We can check that this is indeed correct by looking at a picture:

Show[Graphics[{Red, Line[path1], Green, Line[path2], Blue, Map[
       Point[#] &, obstacles]}]]


Andrzej Kozlowski
Tokyo, Japan





On 30 Oct 2006, at 05:38, Bonny Banerjee wrote:

> Thanks Andrzej. I was trying to simplify the problem and eventually  
> made it trivial.
>
> 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.
>
>
>
>
>
> ----- Original Message -----
> From: "Andrzej Kozlowski" <akoz at mimuw.edu.pl>
To: mathgroup at smc.vnet.net
> Subject: [mg70874] Re: [mg70854] Re: Searching for a function
>
>
> > This adds nothing to the information or the lack of it, in your   
> previous
> > post. If your sets are finite and they have the discrete   
> topology then
> > every function is continuous, so you actually have n^m   
> functions, where n
> > is the cardinality of the soure and m the  cardinality of the  
> target. One
> > can also imagine that what you meant  is a continuous function  
> from an
> > interval to another interval, which  takes a given finite set of  
> points to
> > certain specified images. In  this case you will have infinitely  
> many
> > functions. In fact, the same  is true if you restrict yourself to
> > polynomials of arbitrary degrees.  On the other hand if you restrict
> > yourself to polynomial of a given  degree you can make sure that  
> the answe
> > r is finite. For example, in  your case:
> >
> > A=Range[2,10,2];B=Range[1,10,2]; ls = Transpose[{A, B}];
> >
> >
> > InterpolatingPolynomial[ls,x]
> >
> > x-1
> >
> > In general a polynomial of degree n is determined by its values at n
> > points so this answer is  unique for polynomials of degree <=5. For
> > example, here is how we can get another polynomial which  
> satisfies  all
> > your conditions:
> >
> >
> > AppendTo[ls, {3, 9/2}];
> >
> >
> > f[x_] = Expand[InterpolatingPolynomial[ls, x]]
> >
> > x^5/42 - (5*x^4)/7 + (170*x^3)/21 - (300*x^2)/7 +
> >   (2213*x)/21 - 647/7
> >
> > You can check that this polynomial satisfies all your conditions, in
> > fact:
> >
> >
> > f /@ A == B
> >
> >
> > True
> >
> > Andrzej Kozlowski
> > Tokyo, Japan
> >
> > On 29 Oct 2006, at 12:40, Bonny Banerjee wrote:
> >
> >> I am looking for continuous functions only from set A to set B.   
> Sorry
> >> for
> >> not making it clear.
> >>
> >> --Bonny.
> >>
> >>
> >>
> >>
> >> "Bonny Banerjee" <banerjee.28 at osu.edu> wrote in message
> >> news:ehv8vp$g6f$1 at smc.vnet.net...
> >>> Is it possible for Mathematica to solve this problem:
> >>>
> >>> Given sets A and B, does there exist a function from A to B?  
> If  yes,
> >>> what
> >>> is
> >>> the function?
> >>>
> >>>
> >>> Here is an example:
> >>>
> >>> Let, A = {x such that 0<x<11 and Mod[x,2]==0}
> >>>
> >>> B = {y such that 0<y<11 and Mod[y+1,2]==0}
> >>>
> >>> Then, there exists a function from A to B
> >>>
> >>> y = x - 1
> >>>
> >>>
> >>> Thus, is there a way to specify arbitrary sets A, B, and use
> >>> Mathematica
> >>> to
> >>> figure out whether there exits a function from A to B or not?
> >>>
> >>> Thanks,
> >>> Bonny.
>


  • Prev by Date: Re: Searching for a function
  • Next by Date: Re: Re: Searching for a function
  • Previous by thread: Re: Re: Searching for a function
  • Next by thread: Re: Re: Searching for a function