       Re: Resolve/Reduce is taking forever

• To: mathgroup at smc.vnet.net
• Subject: [mg67258] Re: [mg67217] Resolve/Reduce is taking forever
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Wed, 14 Jun 2006 06:29:44 -0400 (EDT)
• References: <200606130507.BAA23755@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```On 13 Jun 2006, at 14:07, Bonny Banerjee wrote:

> I am trying to write a simple function that determines the
> conditions for a
> curve to be on the left of a straight line. A curve is to the left
> of a
> straight line if each point on the curve is to the left of the
> straight
> line. The curve is specified using parametric equations:
>
> x -> a3Ã?t^3 + a2Ã?t^2 + a1Ã?t + a0
> y -> b1Ã?t + b0
>
> where t is the parameter, 0<=t<=1, and {a0, a1, a2, a3, b0, b1} are
> real
> coefficients. The straight line is specified using two points
> {x1,y1} and
> {x2,y2}.
>
> Here is the function:
>
> isLeftofLine[{x1_, y1_}, {x2_, y2_}, {a0_, a1_, a2_, a3_, b0_, b1_}] =
> Resolve[
>       ForAll[t, 0 <= t <= 1 => fxy[{x1, y1}, {x2, y2}, {a3Ã?t^3 +
> a2Ã?t^2 +
>      a1Ã?t + a0, b1Ã?t + b0}] <= 0],
> {a0, a1, a2, a3, b0, b1}, Reals]
>
> where
>
> fxy[{x1_, y1_}, {x2_, y2_}, {x_, y_}] =
> (x - x1)Ã?(y2 - y1) - (y - y1)Ã?(x2 - x1)
>
> I tried Resolve and Reduce but both are taking forever. I waited
> for more
> than 4 hours but could not get any result from any of them.
> Considering this
> is a simple logical expression with only one universal quantifier,
> I am
> surprised at what might be taking so long.
>
> Any insights would be very helpful. Also, any alternative method
> for solving
> the same problem, such as using any other function in place of
> Reduce/Resolve or using a different representation for the curve or
> straight
> line, would be nice to know. I preferred using parametric equations
> for
> representing the curve as the curve is finite.
>
> Thanks,
> Bonny.
>

First of all, your "function" will not work even, in this form, in a
thousand years, because you are demanding Mathematica to solve a
purely symbolic problem on the right hand side, before any numerical
values have been substituted for x1, x2,y1,y2. This is obviously
impossible (see the comments below) . So as a minimum you need to
replace your immediate assignment = by Delayed assignment :=, and
substitute numerical values for the x's and the y's.  Your function
should then look like this:

isLeftofLine[{x1_, y1_}, {x2_, y2_},{a0_, a1_, a2_, a3_, b0_, b1_}] :=
Resolve[
ForAll[t, 0 <= t <= 1, fxy[{x1, y1}, {x2, y2}, {a3Ã?t^3 +
a2Ã?t^2 +
a1Ã?t + a0, b1Ã?t + b0}] <= 0],
{a0, a1, a2, a3, b0, b1}, Reals]

When you evaluate this with numerical values for the coordinates of
the points you will get a relationship between the a's and b's .
However, even if the problem is now correctly formulated it will take
a very long time to solve it. The algorithm that is needed, called
CylindricalAlgebraicDecomposition, is doubly exponential in the
number of variables (it is the number of variables and not the number
of quantifiers that counts). So let's try first solving a version of
your problem with a smaller number of unknowns, say 4. Here is the
reduced problem.

fxy[{x1_, y1_}, {x2_, y2_}, {x_, y_}] =
(x - x1)Ã?(y2 - y1) - (y - y1)Ã?(x2 - x1)

isLeftofLine[{x1_, y1_}, {x2_, y2_}, {a_, b_, c_, d_}] :=
Resolve[
ForAll[t, 0 <= t <= 1 , fxy[{x1, y1}, {x2, y2}, {t^3 +
a*t^2 + b, c* t + d}] <= 0],
{a, b, c,  d}, Reals]

Now there are only four variables. Let's try some concrete values of
{x1,y1} and {x2,y2}.

In:=
cond=isLeftofLine[{0, 0}, {3, 4}, {a, b, c, d}]

Out=
b â?? Reals && ((a < -6 && ((c <= (1/3)*(8*a + 12) &&
d >= (1/3)*(4*a + 4*b - 3*c + 4)) ||
(Inequality[(1/3)*(8*a + 12), Less, c, LessEqual,
0] && d >= (1/81)*(8*a^3 + 27*c*a + 108*b) +
(1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 +
729*c^3]) || (c > 0 && d >= (4*b)/3))) ||
(-6 <= a <= -3 && ((c <= (1/3)*(8*a + 12) &&
d >= (1/3)*(4*a + 4*b - 3*c + 4)) ||
((1/3)*(8*a + 12) < c < 0 &&
d >= (1/81)*(8*a^3 + 27*c*a + 108*b) +
(1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 +
729*c^3]) || (c >= 0 && d >= (4*b)/3))) ||
(-3 < a < -1 && ((c <= (1/3)*(-a^2 + 2*a + 3) &&
d >= (1/3)*(4*a + 4*b - 3*c + 4)) ||
((1/3)*(-a^2 + 2*a + 3) < c < 0 &&
d >= (1/81)*(8*a^3 + 27*c*a + 108*b) +
(1/81)*Sqrt[64*a^6 + 432*c*a^4 + 972*c^2*a^2 +
729*c^3]) || (c >= 0 && d >= (4*b)/3))) ||
(a >= -1 && ((c <= (1/3)*(4*a + 4) &&
d >= (1/3)*(4*a + 4*b - 3*c + 4)) ||
(c > (1/3)*(4*a + 4) && d >= (4*b)/3))))

We can now use it to check the condition cond for various choices of
{a,b,c,d}, for example

True

So here is the good news and the bad news. I think that if I have
understood you correctly, your problem is solvable in theory. I
strongly doubt,  however, that it is solvable in reasonable time. You
can try out the above on your computer and see how long it takes.
Then remember: the algorithm is double exponential in the number of
variables so 4 hours seems like a very optimistic estimate.

Andrzej Kozlowski
Tokyo, Japan

```

• Prev by Date: Re: Determining continuity of regions/curves from inequalities
• Next by Date: Re: Resolve/Reduce is taking forever
• Previous by thread: Resolve/Reduce is taking forever
• Next by thread: Re: Resolve/Reduce is taking forever