Re: Re: Finding the periphery of a region
- To: mathgroup at smc.vnet.net
- Subject: [mg72038] Re: [mg72013] Re: [mg71983] Finding the periphery of a region
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 9 Dec 2006 06:09:46 -0500 (EST)
- References: <200612071125.GAA28194@smc.vnet.net> <200612081118.GAA20221@smc.vnet.net>
I noticed that I missed the fact that there is an exact way to find
the boundary. Unfortunately, as is usually the case with this kind of
symbolic algebra, it is practical only in simple cases. Here are a
couple of examples that work. As an example, consider the case of the
circle. We define its interior by means of a Boolean valued function:
f[x_, y_] := x^2 + y^2 < 1
Now, this will give us the boundary:
Resolve[ForAll[t, Element[t,Reals] && t > 0, Exists[a, Element[a,Reals],
Exists[b, Element[b,Reals], f[a, b] && (x - a)^2 + (y - b)^2 <
t^2 && !f[x, y]]]]]
(y == -1 && x == 0) || (-1 < y < 1 && (x == -Sqrt[1 - y^2] || x ==
Sqrt[1 - y^2])) ||
(y == 1 && x == 0)
This should work in all cases but the complexity of the algorithm
used is very high so it's not likely to be of mcuh practical use.
Andrzej Kozlowski
On 8 Dec 2006, at 20:18, Andrzej Kozlowski wrote:
>
> On 7 Dec 2006, at 20:25, Bonny Banerjee wrote:
>
>> I have a region specified by a logical combination of equatlities and
>> inequalities. For example, r(x,y) is a region defined as follows:
>>
>> r(x,y) = x^2+y^2<100 or (5<=x<=25 and -10<=y<=10)
>>
>> How do I obtain the periphery of r(x,y)? I am only interested in
>> finite
>> regions i.e. x or y never extends to infinity.
>>
>> Thanks,
>> Bonny.
>>
>>
>
> I guess by the periphery you mean the boundary: the difference
> between the closure and the interior of a semialgebraic set?
> I think in general getting it automatically will be quite difficult.
> In many simple cases you can do it using
>
> Experimental`GenericCylindricalAlgebraicDecomposition. For example,
> it works in both of your examples:
>
>
> Last[Experimental`GenericCylindricalAlgebraicDecomposition[x^2 + y^2
> <= 100, {x, y}]]
>
> x^2 + y^2 - 100 == 0
>
> and
>
>
> Last[Experimental`GenericCylindricalAlgebraicDecomposition[
> 5 <= x <= 25 && -10 <= y <= 10, {x, y}]]
>
>
> 5 - x == 0 || x - 25 == 0 || -y - 10 == 0 || y - 10 == 0
>
> Note, however, that I had to change your first example and use weak
> inequalities. Unfortunately,
> Experimental`GenericCylindricalAlgebraicDecomposition often will give
> you too much:
>
> Last[Experimental`GenericCylindricalAlgebraicDecomposition[
> x^2 + y^2 <= 100 && x^2 + y^2 >= 4, {x, y}]]
>
>
> x - 2 == 0 || x + 2 == 0 || -x^2 - y^2 + 4 == 0 || x^2 + y^2 - 100
> == 0
>
>
> In general in this way you will get a hypersurface containing the
> boundary rather than the boundary itself.
> There is also a more subtle problem involved. The boundary of an
> open region is not always the boundary of the closed region that you
> get by replacing strict inequalities with weak ones. For example
> consider the region given by:
>
> x^3 - x^2 - y^2 > 0 && x < 10
>
> At first glance one might think that the boundary is given by the
> part of the curve x^3 - x^2 - y^2 ==0 for which x<=10 together with
> apiece of the line x==10, but actually using CylindricalDecomposition
> we see that this is not the case:
>
> CylindricalDecomposition[x^3 - x^2 - y^2 > 0 && x < 10,{x, y}]
>
> 1 < x < 10 && -Sqrt[x^3 - x^2] < y < Sqrt[x^3 - x^2]
>
> while
>
>
> CylindricalDecomposition[x^3 - x^2 - y^2 >= 0 && x <= 10, {x, y}]
>
>
> (x == 0 && y == 0) || (x == 1 && y == 0) || (Inequality[1, Less, x,
> LessEqual, 10] &&
> -Sqrt[x^3 - x^2] <= y <= Sqrt[x^3 - x^2])
>
>
> So that the point (0,0) which lies on x^3 - x^2 - y^2==0 does not
> actually lie on the boundary of x^3 - x^2 -y^2>0.
> Of course CylindricalDecomposition contains "the information" about
> the boundary, but extracting it seems tricky, in general. Besides the
> algorithm is much slower than
> Experimental`GenericCylindricalAlgebraicDecomposition.
>
> Andrzej Kozlowski
> Tokyo, Japan
>
>
>
>
- References:
- Finding the periphery of a region
- From: "Bonny Banerjee" <banerjee.28@osu.edu>
- Re: Finding the periphery of a region
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Finding the periphery of a region