[math-fun] Problem for high school algebra ?
We have an _equilateral_ triangle in arbitrary position in standard 3D space with coordinate axes x,y,z. Translate this triangle (without rotations) so that its center becomes the origin. The 3 vertices are P1=(x1,y1,z1), P2=(x2,y2,z2), P3=(x3,y3,z3). We are given x1,y1,x2,y2 (but _not_ the z coordinates). Obviously, x3=-x1-x2, y3=-y1-y2, due to the center being the origin. Find a "simple" expression for the _radius_ of the circumcircle. This problem is trivial in the case that x1^2+y1^2 = x2^2+y2^2 = x2^2+y3^2 = R^2, in which case z1=z2=z3=0, so we are interested in the more difficult case. (Hint: you don't actually need the z coordinates.) (Yes, I do have an answer, which is simpler than I had expected.)
Still trying to stick my two-penn'orth in here, despite proven risk to my dignity ... anyway, you have had the opportunity to admire Henry's rapiers; now you may compare Fred's (Gröbner-basis) blunderbuss. Define a polynomial ring over rationals in 10 variables, in order of elimination z3, z2, z1, y3, y2, y1, x3, x2, x1, R2 ; a set of generators for an ideal { x1^2 + y1^2 + z1^2 - R2, #circumradius squared# x1 + x2 + x3, y1 + y2 + y3, z1 + z2 + z3, #centroid at O# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x1 - x3)^2 + (y1 - y3)^2 + (z1 - z3)^2 ), #equilateral# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x2 - x3)^2 + (y2 - y3)^2 + (z2 - z3)^2 ) } ; and compute its Gröbner-basis (I used Magma, any old CAS should serve). Near the end of the basis should appear a polynomial involving R2 , from which all z's have been eliminated: 3*R2^2 - 4*(x1^2 + x1*x2 + x2^2 + y1^2 + y1*y2 + y2^2)*R2 + 4*(x1*y2 - x2*y1)^2; Solving the quadratic for R2 = R^2 yields circumradius in terms of x-, y-components alone --- sorted! Well, not quite. For one thing, the discriminant must be positive for the roots to be real: this provides a (quartic) inequality constraint on x-, y-components. For another, there are then actually two putative values of R^2 : the physics of the problem suggests that one must always be negative, but this is not obvious from the equation. Similarly, omitting the first ideal generator yields z-components, as roots of the quadratic in z1^2 3*z1^4 - 2*(2*x2^2 + 2*y2^2 + 2*x1*x2 + 2*y1*y2 - x1^2 - y1^2)*z1^2 - (x1^4 + y1^4 + 4*x1^2*x2^2 + 4*y1^2*y2^2 + 4*y1^3*y2 + 4*x1^3*x2 + 4*x1^2*y1*y2 + 4*y1^2*x1*x2 + 8*x1*x2*y1*y2 + 2*y1^2*x1^2); etc. Discriminant and attendant ambiguity are as before, mildly compounded by requiring compatible choices of sign for the z's . Fred Lunnon On 5/8/14, Henry Baker <hbaker1@pipeline.com> wrote:
We have an _equilateral_ triangle in arbitrary position in standard 3D space with coordinate axes x,y,z.
Translate this triangle (without rotations) so that its center becomes the origin.
The 3 vertices are P1=(x1,y1,z1), P2=(x2,y2,z2), P3=(x3,y3,z3).
We are given x1,y1,x2,y2 (but _not_ the z coordinates).
Obviously, x3=-x1-x2, y3=-y1-y2, due to the center being the origin.
Find a "simple" expression for the _radius_ of the circumcircle.
This problem is trivial in the case that x1^2+y1^2 = x2^2+y2^2 = x2^2+y3^2 = R^2, in which case z1=z2=z3=0, so we are interested in the more difficult case.
(Hint: you don't actually need the z coordinates.)
(Yes, I do have an answer, which is simpler than I had expected.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Postscript: some people just can't stop looking for trouble. So we have this nice, simple quadratic equation F(R2) = 0 for R^2 in terms of x-,y-components alone, where F(R2) == 3*R2^2 - 4*(x1^2 + x1*x2 + x2^2 + y1^2 + y1*y2 + y2^2)*R2 + 4*(x1*y2 - x2*y1)^2 . One way to prove would be to express some nonzero multiple of F as a polynomial in the original constraints. There is a method for doing so using Gröbner bases: Append a new variable v_i for each constraint Con(i) ; Replace the ideal generators Con(i) by v_i - Con(i) , except for x1^2 + y1^2 + z1^2 - R2 ; Attaching a further generator u - F(R2) ; Recompute the Gröbner basis, extract the member G containing v_0 but not R2, z's . [ R2 and v_0 are placed early, immediately after z's, in the elimination order list, to avoid the basis computation exploding.] The result is a polynomial G(u, v's, x's, y's) with leading term u^4 and every other term involving some v_i , yielding a certificate that F(R2) = 0 (since the v_i represent constraints which vanish). So let's see this wonderful polynomial, you say (you did say that, didn't you?) Well, I'm afraid it has total degree 16 and 74299 terms! Fred Lunnon On 5/13/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Still trying to stick my two-penn'orth in here, despite proven risk to my dignity ... anyway, you have had the opportunity to admire Henry's rapiers; now you may compare Fred's (Gröbner-basis) blunderbuss.
Define a polynomial ring over rationals in 10 variables, in order of elimination
z3, z2, z1, y3, y2, y1, x3, x2, x1, R2 ;
a set of generators for an ideal
{ x1^2 + y1^2 + z1^2 - R2, #circumradius squared# x1 + x2 + x3, y1 + y2 + y3, z1 + z2 + z3, #centroid at O# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x1 - x3)^2 + (y1 - y3)^2 + (z1 - z3)^2 ), #equilateral# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x2 - x3)^2 + (y2 - y3)^2 + (z2 - z3)^2 ) } ;
and compute its Gröbner-basis (I used Magma, any old CAS should serve). Near the end of the basis should appear a polynomial involving R2 , from which all z's have been eliminated:
3*R2^2 - 4*(x1^2 + x1*x2 + x2^2 + y1^2 + y1*y2 + y2^2)*R2 + 4*(x1*y2 - x2*y1)^2;
Solving the quadratic for R2 = R^2 yields circumradius in terms of x-, y-components alone --- sorted!
Well, not quite. For one thing, the discriminant must be positive for the roots to be real: this provides a (quartic) inequality constraint on x-, y-components. For another, there are then actually two putative values of R^2 : the physics of the problem suggests that one must always be negative, but this is not obvious from the equation.
Similarly, omitting the first ideal generator yields z-components, as roots of the quadratic in z1^2
3*z1^4 - 2*(2*x2^2 + 2*y2^2 + 2*x1*x2 + 2*y1*y2 - x1^2 - y1^2)*z1^2 - (x1^4 + y1^4 + 4*x1^2*x2^2 + 4*y1^2*y2^2 + 4*y1^3*y2 + 4*x1^3*x2 + 4*x1^2*y1*y2 + 4*y1^2*x1*x2 + 8*x1*x2*y1*y2 + 2*y1^2*x1^2);
etc. Discriminant and attendant ambiguity are as before, mildly compounded by requiring compatible choices of sign for the z's .
Fred Lunnon
On 5/8/14, Henry Baker <hbaker1@pipeline.com> wrote:
We have an _equilateral_ triangle in arbitrary position in standard 3D space with coordinate axes x,y,z.
Translate this triangle (without rotations) so that its center becomes the origin.
The 3 vertices are P1=(x1,y1,z1), P2=(x2,y2,z2), P3=(x3,y3,z3).
We are given x1,y1,x2,y2 (but _not_ the z coordinates).
Obviously, x3=-x1-x2, y3=-y1-y2, due to the center being the origin.
Find a "simple" expression for the _radius_ of the circumcircle.
This problem is trivial in the case that x1^2+y1^2 = x2^2+y2^2 = x2^2+y3^2 = R^2, in which case z1=z2=z3=0, so we are interested in the more difficult case.
(Hint: you don't actually need the z coordinates.)
(Yes, I do have an answer, which is simpler than I had expected.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Post^2script: The natural ordering of the variables puts u (standing for the polynomial F(R^2) which we want to prove vanishes) last, since we don't want it eliminated at all --- but this simply blew up when I tried to compute a basis (1.5 hrs + 1 Gb and climbing when last seen). Counter-intuitively moving u along with R^2 to an earlier position quickly yielded a quartic in P with ~75K terms, which sort of did the job. But why stop there? At this stage, it doesn't matter whether z's appear in the certificate G ; all we need is that every term has involves either u or some v (standing for constraint). So avoid complications from eliminating z's by shoving R2,u all the way to the front of the list, and bingo: second member of the basis comes out as G = u - (polynomial in x,y,z's , and v's in all terms) ! It's 85 terms long, but that's quite some improvement on 75K ... This is good example of how the Gröbner blunderbuss can flatten a problem without requiring any further understanding of geometric details, the downside being that it is very liable to misfire unless carefully primed. Fred Lunnon On 5/15/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Postscript: some people just can't stop looking for trouble.
So we have this nice, simple quadratic equation F(R2) = 0 for R^2 in terms of x-,y-components alone, where
F(R2) == 3*R2^2 - 4*(x1^2 + x1*x2 + x2^2 + y1^2 + y1*y2 + y2^2)*R2 + 4*(x1*y2 - x2*y1)^2 .
One way to prove would be to express some nonzero multiple of F as a polynomial in the original constraints.
There is a method for doing so using Gröbner bases: Append a new variable v_i for each constraint Con(i) ; Replace the ideal generators Con(i) by v_i - Con(i) , except for x1^2 + y1^2 + z1^2 - R2 ; Attaching a further generator u - F(R2) ; Recompute the Gröbner basis, extract the member G containing v_0 but not R2, z's .
[ R2 and v_0 are placed early, immediately after z's, in the elimination order list, to avoid the basis computation exploding.]
The result is a polynomial G(u, v's, x's, y's) with leading term u^4 and every other term involving some v_i , yielding a certificate that F(R2) = 0 (since the v_i represent constraints which vanish).
So let's see this wonderful polynomial, you say (you did say that, didn't you?) Well, I'm afraid it has total degree 16 and 74299 terms!
Fred Lunnon
On 5/13/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Still trying to stick my two-penn'orth in here, despite proven risk to my dignity ... anyway, you have had the opportunity to admire Henry's rapiers; now you may compare Fred's (Gröbner-basis) blunderbuss.
Define a polynomial ring over rationals in 10 variables, in order of elimination
z3, z2, z1, y3, y2, y1, x3, x2, x1, R2 ;
a set of generators for an ideal
{ x1^2 + y1^2 + z1^2 - R2, #circumradius squared# x1 + x2 + x3, y1 + y2 + y3, z1 + z2 + z3, #centroid at O# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x1 - x3)^2 + (y1 - y3)^2 + (z1 - z3)^2 ), #equilateral# ( (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 ) - ( (x2 - x3)^2 + (y2 - y3)^2 + (z2 - z3)^2 ) } ;
and compute its Gröbner-basis (I used Magma, any old CAS should serve). Near the end of the basis should appear a polynomial involving R2 , from which all z's have been eliminated:
3*R2^2 - 4*(x1^2 + x1*x2 + x2^2 + y1^2 + y1*y2 + y2^2)*R2 + 4*(x1*y2 - x2*y1)^2;
Solving the quadratic for R2 = R^2 yields circumradius in terms of x-, y-components alone --- sorted!
Well, not quite. For one thing, the discriminant must be positive for the roots to be real: this provides a (quartic) inequality constraint on x-, y-components. For another, there are then actually two putative values of R^2 : the physics of the problem suggests that one must always be negative, but this is not obvious from the equation.
Similarly, omitting the first ideal generator yields z-components, as roots of the quadratic in z1^2
3*z1^4 - 2*(2*x2^2 + 2*y2^2 + 2*x1*x2 + 2*y1*y2 - x1^2 - y1^2)*z1^2 - (x1^4 + y1^4 + 4*x1^2*x2^2 + 4*y1^2*y2^2 + 4*y1^3*y2 + 4*x1^3*x2 + 4*x1^2*y1*y2 + 4*y1^2*x1*x2 + 8*x1*x2*y1*y2 + 2*y1^2*x1^2);
etc. Discriminant and attendant ambiguity are as before, mildly compounded by requiring compatible choices of sign for the z's .
Fred Lunnon
On 5/8/14, Henry Baker <hbaker1@pipeline.com> wrote:
We have an _equilateral_ triangle in arbitrary position in standard 3D space with coordinate axes x,y,z.
Translate this triangle (without rotations) so that its center becomes the origin.
The 3 vertices are P1=(x1,y1,z1), P2=(x2,y2,z2), P3=(x3,y3,z3).
We are given x1,y1,x2,y2 (but _not_ the z coordinates).
Obviously, x3=-x1-x2, y3=-y1-y2, due to the center being the origin.
Find a "simple" expression for the _radius_ of the circumcircle.
This problem is trivial in the case that x1^2+y1^2 = x2^2+y2^2 = x2^2+y3^2 = R^2, in which case z1=z2=z3=0, so we are interested in the more difficult case.
(Hint: you don't actually need the z coordinates.)
(Yes, I do have an answer, which is simpler than I had expected.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred Lunnon -
Henry Baker