Determining continuity of regions/curves from inequalities
in [Mathematica]
|
From: Bonny Banerjee on 13 Jun 2006 01:11 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.
From: Andrzej Kozlowski on 14 Jun 2006 06:44 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 ss[[1]]/.Thread[{x,y,z}->{2,0,0}] Out[11]= False In[12]:= ss[[2]]/.Thread[{x,y,z}->{2,0,0}] Out[12]= True So (2,0,0) lies in the first component. Now consider (-1/2,0,0) ss[[1]] /. Thread[{x, y, z} -> {-2^(-1), 0, 0}] True ss[[2]] /. 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
From: Andrzej Kozlowski on 14 Jun 2006 06:49 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, > > Thanks for your response. > > 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" > Sent: Tuesday, June 13, 2006 10:37 AM > Subject: Re: Determining continuity of regions/curves > from inequalities > > >> >> 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 >> >> >> ss[[1]]/.Thread[{x,y,z}->{2,0,0}] >> >> Out[11]= >> False >> >> In[12]:= >> ss[[2]]/.Thread[{x,y,z}->{2,0,0}] >> >> Out[12]= >> True >> >> So (2,0,0) lies in the first component. Now consider (-1/2,0,0) >> >> >> ss[[1]] /. Thread[{x, y, z} -> {-2^(-1), 0, 0}] >> >> >> True >> >> >> ss[[2]] /. 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>
From: Andrzej Kozlowski on 14 Jun 2006 06:57 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 so far I have not thought about this. I have thought about it on the 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 Combinatorica package to answer your question. 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, >> >> Thanks for your response. >> >> 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" >> Sent: Tuesday, June 13, 2006 10:37 AM >> Subject: Re: Determining continuity of regions/curves >> from inequalities >> >> >>> *This message was transferred with a trial version of CommuniGate >>> (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 >>> >>> >>> ss[[1]]/.Thread[{x,y,z}->{2,0,0}] >>> >>> Out[11]= >>> False >>> >>> In[12]:= >>> ss[[2]]/.Thread[{x,y,z}->{2,0,0}] >>> >>> Out[12]= >>> True >>> >>> So (2,0,0) lies in the first component. Now consider (-1/2,0,0) >>> >>> >>> ss[[1]] /. Thread[{x, y, z} -> {-2^(-1), 0, 0}] >>> >>> >>> True >>> >>> >>> ss[[2]] /. 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> >
From: Carl K. Woll on 15 Jun 2006 03:37
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. > The function SemialgebraicComponents in the package Algebra`AlgebraicInequalities may help. From the help browser: "The package provides a function for solving systems of strong polynomial inequalities in one or more unknowns. To be precise, SemialgebraicComponents[ineqs, vars] gives a finite set of solutions of the system of inequalities. That is, within the set of solutions, any solution can be connected by a continuous path to a solution in the finite set. The variable ineqs is a list of strong inequalities, where both sides of each inequality are polynomials in variables vars with rational coefficients. In other words, SemialgebraicComponents[ineqs, vars] gives at least one point in each connected component of the open semialgebraic set defined by inequalities ineqs. " Needs["Algebra`AlgebraicInequalities`"] First example: x>2 && y>0 SemialgebraicComponents accepts a list of inequalities: In[6]:= SemialgebraicComponents[{x>2,y>0},{x,y}] Out[6]= {{3,1}} Only one point is returned, so the region is connected. Second example: (x<2 && y<0) || (x>2 && y>0) This example is not a list of inequalities due to the Or. However, in this case it is easy to construct an equivalent inequality that encompasses the same region: In[5]:= SemialgebraicComponents[(x-2)y>0,{x,y}] Out[5]= {{0,-1},{3,1}} There are two components, so the region is not connected. Carl Woll Wolfram Research |