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: [mg70875] Re: [mg70854] Re: Searching for a function
  • From: "Bonny Banerjee" <banerjee.28 at osu.edu>
  • Date: Mon, 30 Oct 2006 05:33:08 -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> <96EFF006-FE33-4D5C-BB08-BD57CA39E8DB@mimuw.edu.pl>

Thanks Andrzej. I am aware of the solution you mentioned. What you presented 
is an "algorithm" for computing whether two paths are homotopic or not. What 
I want is a function with the properties I mentioned. I want a function 
because I am going to analyze the properties of that function for further 
reasoning. An algorithm will not serve that purpose.

An example of F 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 how do I prove that there does not exist any function for Path1 and 
Path2 to be homotopic? That is where I am stuck.

Any help will be appreciated.

Thanks,
Bonny.




----- Original Message ----- 
From: "Andrzej Kozlowski" <akoz at mimuw.edu.pl>
To: mathgroup at smc.vnet.net
Subject: [mg70875] Re: [mg70854] Re: Searching for a function


> 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: [mg70875] 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: 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