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