       Re: Determining continuity of regions/curves from inequalities

• To: mathgroup at smc.vnet.net
• Subject: [mg67366] Re: [mg67216] Determining continuity of regions/curves from inequalities
• Date: Tue, 20 Jun 2006 02:14:55 -0400 (EDT)
• References: <200606130506.BAA23751@smc.vnet.net> <E473D604-0718-42F2-B6F4-2444A2712032@mimuw.edu.pl> <001f01c68f2c\$1520ec50\$6501a8c0@bblaptop> <DFFCE756-9C3D-4848-B4F6-E6DC38750D4B@mimuw.edu.pl> <90D474EF-9989-4847-9060-306CC851F3F2@mimuw.edu.pl>
• Sender: owner-wri-mathgroup at wolfram.com

```The problem has been well researched (for instance search for
there is no implementation in Mathematica. If the number of
variables is <= 3, InequalityPlot(3D) can be used to find
the connected components, but of course plots are subject to
numeric computation error.

Best Regards,

Wolfram Research

Andrzej Kozlowski wrote:
> I think I now have an idea of how it might be done with Mathematica  in
> a special case, when the region described by the inequalities is
> bounded. Perhaps the method can be extended to a unbounded region,  but
> train on my way to my university and I have to give a lecture in  less
> than an hour, so I can't work out the details not to mention  trying to
> implement it. But the idea is as follows:
>
> Problem. Given a set of algebraic inequalities with a bounded,  possibly
> disconnected  solution region and two points in the region,  determine
> if the points are in the same connected component.
>
> The idea is this. Find the cylindrical decomposition of the region  and
> the cylinders that contain the two points. Now, triangulate these
> cylinders in such a way that the points become vertices of the
> triangulation and the whole region becomes a planar graph, with these
> two points as vertices. Construct the Adjacency matrix of the
> triangulation. Now you can use the function ConnectedComponents of  the
>
> In principle I can see (I think) how to implement this, although it
> would take some work and after all might not be computationally  viable
> except in simple cases. There may also be well known and more  efficient
> algorithms that do this: in particular there should be an  algorithm for
> triangulating any semi-algebraic set (actually such  algorithms are well
> known - the issue is if there are efficient  implementations-which is
> something I do no know). However, I am sure  Adam Strzebonski knows ;-)
>
> Andrzej Kozlowski
>
>
> On 14 Jun 2006, at 06:40, Andrzej Kozlowski wrote:
>
>> I think I gave a misleading impression. As it name suggests,
>> CylindricalDecomposition shows the number of cylinders, not
>> components. The number of cylinders in cylindrical decomposition is
>> never smaller than the number of components, but it will often be
>> larger, as in your example.
>> I do not think it will be easy to write a function, or at least an
>> efficient functions,  that will counts the number of components  in
>> Mathematica. If you need to do this for complicated cases you will
>> need to use software that computes the homology  (the zeroth  homology
>> group is generated by the components) of semi-algebraic  sets.
>> However, I do not know, just off hand, of any program that  can do it.
>>
>> Andrzej Kozlowski
>>
>>
>>
>> On 14 Jun 2006, at 05:58, Bonny Banerjee wrote:
>>
>>> Hi Andrzej,
>>>
>>>
>>> I am not sure that I made my problem clear enough. I was looking  for
>>> a way to figure out whether there exists any path to travel  from one
>>> point to another lying entirely within a given region. If  such a
>>> path exists, I would call that region continuous, otherwise  not.
>>>
>>> The procedure that you specified -- to count the number of Or's in
>>> the CylindricalDecomposition of a logical expression -- does not
>>> serve that purpose. An example is provided in the attached file
>>> where the region is continuous but CylindricalDecomposition gives  8
>>> components. I would have liked the output to be one component.
>>>
>>> A possible way of doing this would be to grow regions from each of
>>> the two points with different colors (say blue and green) in all
>>> directions. If, at any point, the two colors meet, then the region
>>> is continuous. If the entire boundary is filled but the colors
>>> haven't met, then the region is discontinuous with respect to  those
>>> two points, i.e. those two points cannot be joined by a  path.
>>> However, I do not know whether Mathematica has any functions
>>> suitable for such computations.
>>>
>>> --Bonny.
>>>
>>>
>>> ----- Original Message ----- From: "Andrzej Kozlowski"
To: mathgroup at smc.vnet.net
>>> <akoz at mimuw.edu.pl>
>>> Sent: Tuesday, June 13, 2006 10:37 AM
>>> Subject: [mg67366] Re: [mg67216] Determining continuity of regions/curves  from
>>> inequalities
>>>
>>>
>>>> (tm) Pro*
>>>>
>>>> On 13 Jun 2006, at 14:06, Bonny Banerjee wrote:
>>>>
>>>>> Is there an easy way in Mathematica to determine whether the
>>>>> region  or curve
>>>>> formed by a system of inequalities is continuous or not?
>>>>>
>>>>> For example, the output of some function (e.g. Reduce) might be  as
>>>>> follows:
>>>>>
>>>>> x>2 && y>0
>>>>>
>>>>> which forms a continuous region. Again, the following output
>>>>>
>>>>> (x<2 && y<0) || (x>2 && y>0)
>>>>>
>>>>> is not continuous. Similarly, for curves.
>>>>>
>>>>> Given such a system of inequalities, how to determine whether the
>>>>> region/curve it forms is continuous or not? Or in other words,  if
>>>>> I  pick any
>>>>> two random points, say P1 and P2, lying on the output curve/
>>>>> region,  does
>>>>> there exist a continuous path lying entirely within the output
>>>>> curve/region
>>>>> from P1 to P2?
>>>>>
>>>>> Any help will be appreciated.
>>>>>
>>>>> Thanks,
>>>>> Bonny.
>>>>>
>>>>
>>>> In general the answer is complicated, but in cases like the above
>>>> you  can tell how many components there are buy looking at how  many
>>>> Or's  appear in the CylindricalDecomposition of your set of
>>>> inequalities.  For example consider
>>>>
>>>> ss = CylindricalDecomposition[x^3 + y^2 + z^4 < x^5,
>>>>    {x, y, z}]
>>>>
>>>>
>>>> (-1 < x < 0 && -Sqrt[x^5 - x^3] < y < Sqrt[x^5 - x^3] &&
>>>>    -(x^5 - x^3 - y^2)^(1/4) < z < (x^5 - x^3 - y^2)^
>>>>      (1/4)) || (x > 1 && -Sqrt[x^5 - x^3] < y <
>>>>     Sqrt[x^5 - x^3] && -(x^5 - x^3 - y^2)^(1/4) < z <
>>>>     (x^5 - x^3 - y^2)^(1/4))
>>>>
>>>> so there are two components. Take the point (2,0,0}. We have
>>>>
>>>>
>>>>
>>>> Out=
>>>> False
>>>>
>>>> In:=
>>>>
>>>> Out=
>>>> True
>>>>
>>>> So (2,0,0) lies in the first component. Now consider (-1/2,0,0)
>>>>
>>>>
>>>> ss[] /. Thread[{x, y, z} -> {-2^(-1), 0, 0}]
>>>>
>>>>
>>>> True
>>>>
>>>>
>>>> ss[] /. Thread[{x, y, z} -> {-2^(-1), 0, 0}]
>>>>
>>>> False
>>>>
>>>> so (-1/2,0,1} lies in the second component. The two cannot be
>>>> connected by a curve lying within the region satisfying the
>>>> inequality. You can see the two components as follows:
>>>>
>>>>
>>>> <<Graphics`InequalityGraphics`
>>>>
>>>>
>>>> InequalityPlot3D[x^3+y^2+z^4<x^5,{x,-3,3},{y},{z}]
>>>>
>>>> Andrzej Kozlowski
>>>>
>>>>
>>>> <Trial.nb>
>>
>>
>

```

• Prev by Date: Numerical Integration
• Next by Date: Re: Re: standard errors and confidence intervals in NonlinearRegress
• Previous by thread: Re: Determining continuity of regions/curves from inequalities
• Next by thread: Re: Re: Determining continuity of regions/curves from inequalities