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.
>>
>
- References:
- Re: Searching for a function
- From: "Bonny Banerjee" <banerjee.28@osu.edu>
- Re: Searching for a function