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. >

**References**:**Re: Searching for a function***From:*"Bonny Banerjee" <banerjee.28@osu.edu>