RE: Resolve/Reduce is taking forever

*To*: mathgroup at smc.vnet.net*Subject*: [mg67261] RE: [mg67217] Resolve/Reduce is taking forever*From*: "David Park" <djmp at earthlink.net>*Date*: Wed, 14 Jun 2006 06:29:49 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Bonny, The following uses the Ted Ersek RootSearch package, which you can obtain from MathSource at WRI. I have done three specific cases and will leave it to you to work out a general routine. Needs["Ersek`RootSearch`"] Here is a curve definition and three curves. curve[{a0_, a1_, a2_, a3_}, {b0_, b1_}][t_] := {a3*t^3 + a2*t^2 + a1*t + a0, b1*t + b0} curve1 = curve[{8, -2, 3, -4}, {0, 1}][t] curve2 = curve[{1, 3, 3, 2}, {1, -3}][t] curve3 = curve[{1, -4, 0, 4}, {0, 4}][t] {8 - 2*t + 3*t^2 - 4*t^3, t} {1 + 3*t + 3*t^2 + 2*t^3, 1 - 3*t} {1 - 4*t + 4*t^3, 4*t} Here is a line, which is oriented from the first point to the second point.. Line[{{2, -3}, {6, 5}}]; We want to know if the curve segments 0 <= t <= 1 is to the left of the line. One approach to solving this problem is to translate and rotate the plane so that the line segment lies along the positive y axis. Then the curve segment is on the left if the x coordinate is always less than zero. I find that the easiest method for doing this is to use complex algebra. Let z1 and z2 be the end points of the line in the complex plane. z1 = 2 - 3I; z2 = 6 + 5I; Shift and rotate objects in the plane so that the line is along the imaginary axis. We want the solution that gives a positive value. Re[Exp[I phi](z2 - z1)] == 0; ComplexExpand[%] phisols = RootSearch[%, {phi, 0, 2Pi}] Im[Exp[I phi](z2 - z1)] /. phisols phi0 = phi /. First@phisols giving.. 4 Cos[phi] - 8 Sin[phi] == 0 {{phi -> 0.463648}, {phi -> 3.60524}} {8.94427, -8.94427} 0.463648 To check if the curve segment is on the left we can check that the maximum real value is negative. To check that it is on the right we can check that the minimum real value is positive. If the maximum and minimum real values are of opposite sign the curve segment crosses the line, The first curve segment is entirely on the right. curve1 /. {x_, y_} -> x + I y Re[Exp[I phi0](% - z1)] // ComplexExpand NMaximize[{%, 0 <= t <= 1}, t] NMinimize[{%%, 0 <= t <= 1}, t] giving... 8 - (2 - I)*t + 3*t^2 - 4*t^3 4.024922359499621 - 2.23606797749979*t + 2.6832815729997477*t^2 - 3.5777087639996634*t^3 {4.024922359499621, {t -> 0.}} {0.894427, {t -> 1.}} The second curve segment cuts across the line. curve2 /. {x_, y_} -> x + I y Re[Exp[I phi0](% - z1)] // ComplexExpand NMaximize[{%, 0 <= t <= 1}, t] NMinimize[{%%, 0 <= t <= 1}, t] giving... 1 + I*(1 - 3*t) + 3*t + 3*t^2 + 2*t^3 -2.6832815729997477 + 4.024922359499621*t + 2.6832815729997477*t^2 + 1.7888543819998317*t^3 {5.81378, {t -> 1.}} {-2.68328, {t -> 0.}} The third curve segment is entirely on the left. curve3 /. {x_, y_} -> x + I y Re[Exp[I phi0](% - z1)] // ComplexExpand NMaximize[{%, 0 <= t <= 1}, t] NMinimize[{%%, 0 <= t <= 1}, t] giving... 1 - (4 - 4*I)*t + 4*t^3 -2.23606797749979 - 5.366563145999495*t + 3.5777087639996634*t^3 {-2.23607, {t -> 0.}} {-4.76589, {t -> 0.707107}} David Park djmp at earthlink.net http://home.earthlink.net/~djmp/ From: Bonny Banerjee [mailto:banerjee at cse.ohio-state.edu] To: mathgroup at smc.vnet.net 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.