Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

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: [mg70881] Re: [mg70854] Re: Searching for a function
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Mon, 30 Oct 2006 05:33:21 -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> <086e01c6fbba$baee8340$1e0110ac@bblaptop> <E4FF396B-81CC-41DD-8A57-CE514D9AB566@mimuw.edu.pl> <089401c6fbc8$2f480d80$1e0110ac@bblaptop>

I do not think any such general algorithms exist and therefore cannot  
be known to Mathematica.
(My main subject is "homotopy theory" - part of algebraic topology,   
and though admittedly, in homotopy theory normally it is only  
existence or non-existence of homotopies that matters, I have also  
looked at a number of text  on constructive homotopy methods (e.g. in  
equation solving)  and I never seen any such general algorithm.)
In certain special cases, ( dealing with smooth curves or piecewise  
curves) on can try to find smooth homotopies by formulating a  
suitable boundary value problem and using PDE methods to solve it.  
(You would still need to formulate the BVP by hand).  However, this  
will work only in special cases, and moreover, in most of them you  
are likely to end up only with an InterpolatingFunction rather than  
an explicit formula.

Andrzej Kozlowski


On 30 Oct 2006, at 11:07, Bonny Banerjee wrote:

> My problem is: Given two paths and a set of obstacles, find out  
> whether the two paths are homotopic or not. If they are, what is  
> the homotopy function?
>
> Your algorithm only answers whether two paths are homotopic or not.  
> It does not provide any homotopy function in case they are  
> homotopic. I too think, as you say, that I will have to come up  
> with candidate functions and verify them using Mathematica. But it  
> would have been nice if Mathematica could come up with the  
> appropriate function automatically. That is what I was looking for.
>
> Thanks anyway,
> Bonny.
>
>
>
> ----- Original Message ----- From: "Andrzej Kozlowski"  
To: mathgroup at smc.vnet.net
> Subject: [mg70881] Re: [mg70854] Re: Searching for a function
>
>
>> I still find your message confusing or even contradictory.  You  
>> write:
>>
>> But how do I prove that there does not exist any function for  
>> Path1  and Path2 to be homotopic?
>>
>> Well, of course the argument I presented shows that there is no   
>> homotopy between the two paths you gave in your example, and that   
>> means not just a linear homotopy but any homotopy whatever.
>>
>>  Perhaps what you are really asking is something quite different?   
>> Maybe have two paths which are homotopic, but not by a linear   
>> homotopy, and you would like to find some other homotopy between   
>> them? It is easy to create such examples, but I won't bother with   
>> doing it here. Well, unfortunately, I am pretty sure, there is  
>> fully  algorithmic method to solve this problem. Even though you  
>> can prove  that some homotopy must exist, you still have to  
>> construct candidates  "by hand", and you can only use Mathematica  
>> to decide if your  candidate works or not.
>> In most simple numerical applications of homotopy methods linear  
>> homotopies, like in your examples are used, and it is not  
>> difficult  to check if they work or not. You can also prove, as I  
>> pointed out  earlier, that no homotopy exists, in the cases when  
>> it does not  exist. But the troublesome cases are when a homotopy  
>> is known to  exist  but a simple linear one does not work. I do  
>> not believe  Mathematica or any other computer program can deal  
>> with such cases  without human direction.
>>
>> Andrzej Kozlowski
>>
>>
>> On 30 Oct 2006, at 09:31, Bonny Banerjee wrote:
>>
>>> 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"  
To: mathgroup at smc.vnet.net
>>> Subject: [mg70881] Re: [mg70854] Re: Searching for a function
>>>
>>>
>>>> *This message was transferred with a trial version of  
>>>> 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: [mg70881] Re: [mg70854] Re: Searching for a function
>>>>>
>>>>>
>>>>> > *This message was transferred with a trial version of  
>>>>> (tm) Pro*
>>>>> > 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
  • Previous by thread: Re: Re: Searching for a function
  • Next by thread: Re: Searching for a function