From: Cassiano Durand Newsgroups: sci.math.research Subject: Placement of points and lines Date: Fri, 17 Apr 1998 15:27:43 -0500 Greetings, I would like to compute ALL the possible placements (with real coordinates) of 3 points (A, B, C) and 3 lines (Q, R, S) in R^3 where (1) The angles between each pair of lines are equal to 90o. (2) The distances between each pair of points are known (dAB, dAC, dBC) (3) The distances between each pair line-point are also known (dAQ, dAR, dAS, dBQ, dBR, dBS, dCQ, dCR, dCS). Assuming that the configuration is not degenerate (distances not 0, lines are not coincident, etc) we have only a finite number of real solutions. I'd like your opinion about the approaches one could use to solve this problem efficiently. Thank you Cassiano -- ______________________________________________________ Cassiano Durand phone: 765-494-6002 Computer Science Department fax: 765-494-0739 Purdue University West Lafayette, IN 47907-1398 _______________________________________________________ ============================================================================== From: rusin@math.niu.edu (Dave Rusin) Newsgroups: sci.math.research Subject: Re: Placement of points and lines Date: 27 Apr 1998 14:05:41 GMT In article <3537BB3F.E61CB311@alcor.cs.purdue.edu>, Cassiano Durand wrote: >I would like to compute ALL the >possible placements (with real coordinates) of 3 points (A, B, C) >and 3 lines (Q, R, S) in R^3 where > >(1) The angles between each pair of lines are equal to 90o. > >(2) The distances between each pair of points are known (dAB, dAC, dBC) > >(3) The distances between each pair line-point are also known >(dAQ, dAR, dAS, dBQ, dBR, dBS, dCQ, dCR, dCS). > >Assuming that the configuration is not degenerate >(distances not 0, lines are not coincident, etc) we have only a finite >number of real solutions. I'd like your opinion about the approaches >one could use to solve this problem efficiently. One may cast this as asking for solutions to a set of polynomial equations. If you had emphasized "compute", then efficient solutions are easy (e.g. Newton's method). But since you emphasized "all", it seems to me you need to use techniques in algebraic geometry at least to know the _number_ of solutions. Indeed, sufficient tools exist today to turn the problem into a collection of problems of the form "solve 0=f1(x)=f2(x,y)=f3(x,y,z)=... for x,y,z,..." with each f_i being polynomial. The solution of those subproblems is also quite easy (although since you specified "real coordinates", there may be some subtleties regarding efficiency -- e.g. one might want to know which roots x of f1 will allow a _real_ root y of f2.) Even the _creation_ of those subproblems is, um, straightforward -- that's what the techniques of Groebner bases etc. are for. Unfortunately, the creation of these subproblems is not nearly as "efficient" as you might be hoping for. I estimate that I could compute all solutions for a given set of initial data but only with _a day or two_ of CPU time on a workstation with 100Mb RAM. Here's what I did in some examples. (I'd be happy to hear of suggestions for improvement.) First off: how can you assert finitude of the solution set? Certainly any solution can be translated and rotated to get more solutions, so I suppose you want _equivalence classes_ under these motions. But up to rotation, you can assume the three lines are parallel to the coordinate axes; it's easy then to choose a translation after which the lines are the sets of points L1 = { (t, q, -r) : t is real } L2 = { (-p, t, r) : t is real } L3 = { (p, -q, t) : t is real } for some real p, q, r. (In the generic case the Euclidean motions leading to such a presentation are determined to within the group of order 8 generated by coordinate reflections; we can remove ambiguity by assuming p,q,r > 0.) Then if the coordinates of the points are (x_i,y_i,z_i) for i=1,2,3, then we have 12 variables related by 12 equations: three of the form (x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2 = d_ij and nine including (y_1 - q)^2 + (z_1 + r)^2 = dAQ^2 and others similar. Now, these equations define an ideal I in R[p,q,r,x1,...,z3] where R is your coefficient ring. You wish to know the variety determined by this ideal. If the variety is a finite set of points, each of them determines a prime ideal P_i in this ring; the intersection of those primes is the radical of the ideal I. So what you want is precisely a decomposition of the radical of I as an intersection of prime ideals P_i, each generated by a sequence of polynomials f1(p)=0, f2(p,q)=0, ... Ideally, I suppose, R would be an extension of the rationals which contains the 12 indeterminates dAB, dAQ, ..., so that you could do the computations formally and with exact arithmetic, and then for specific choice of initial data you simply plug in the values of these parameters (you have indicated you're not concerned about the degenerate cases). In principle, you can get this without intervention from Magma, for example: K:=IntegerRing(); R := FunctionField(K, 12); P:=PolynomialRing(R,12,"lex"); f3:=(x1-x2)^2+(y1-y2)^2+(z1-z2)^2-a1; f2:=(x1-x3)^2+(y1-y3)^2+(z1-z3)^2-a2; f1:=(x3-x2)^2+(y3-y2)^2+(z3-z2)^2-a3; e11:=(y1-q)^2+(z1+r)^2-a4; e12:=(z1-r)^2+(x1+p)^2-a5; e13:=(x1-p)^2+(y1+q)^2-a6; e21:=(y2-q)^2+(z2+r)^2-a7; e22:=(z2-r)^2+(x2+p)^2-a8; e23:=(x2-p)^2+(y2+q)^2-a9; e31:=(y3-q)^2+(z3+r)^2-a10; e32:=(z3-r)^2+(x3+p)^2-a11; e33:=(x3-p)^2+(y3+q)^2-a12; I:=ideal

; RadicalDecomposition(I); Perhaps someone who reads this message in the year 2010 will enter these commands and get their answer in minutes, but with 1998 machines this is hopeless -- memory usage swells past the 100MB available on my machines in minutes, and I'm sure that even if memory were available, execution time would be in weeks, years, or lifetimes. On the other hand, there are several tricks which may make the computation feasible: each seems to reduce memory use or execution time or both. 1. Rather than treat the initial parameters a_i as indeterminates, given them assigned values. (I assume them to be rational so I can perform all calculations integrally.) "Most" choices of the a_i will lead to varieties of the same cardinality, but of course you won't know in advance whether or not your choices of a_i were "generic". In Magma, the parameters are assigned simply with commands like a1:=1;a2:=2;a3:=3;a4:=5;a5:=7;a6:=11;a7:=12;a8:=17;a9:=25; a10:=31;a11:=197;a12:=1001; after the declaration of the ring. 2. Rather than work over the integers, work mod p for several large primes and then lift with the Chinese Remainder Theorem. Again, most but not all primes will show the same size variety. In order for the lift to integers to work, you have to know that the coefficients integrally are "small", which is something of a gamble. The commands are, say, p:=10000000019; R:=GF(p); I'm not really sure why the rational calculations take so much longer, but that's my experience. (They don't seem to consume any more memory.) 3. Rather than study the variety in R^12, look only for the projection to R^3 which retains only the coordinates p, q, and r. This is sufficient in practice since these three parameters locate the lines; then from the initial data there are at most 8 possible locations for each of the three points; a check of the 8^3 combinations will show which ones have the correct inter-point distances. The command is J:=EliminationIdeal(I,9); 4. Rather than ask for the complete computation of the prime ideals, just simplify the presentation of the ideal a bit. The command Groebner(J); will re-formulate the presentation of the ideal using Groebner bases which, if lexicographic ordering has been selected, may be close enough to the desired format to enable reading off the equations which really determine the values of the variables. Some commands of intermediate difficulty and value might be Radical(J); ProbableRadicalDecomposition(J); Variety(J); VarietySizeOverAlgebraicClosure(J); 5. One factor which determines the difficulty of a problem is the size of the solution set. In this problem, there are many more solutions than is really necessary: we have already noted there is an 8-fold symmetry in the solution set. One way out of this is to solve only for p^2, q^2, and r^2 rather than p, q, and r. This is a little tricky since those symmetries also change the signs of the x_i, y_i, and z_i. Since you have stated you're not interested in what happens in degenerate cases, let me assume that p, q, and r aren't zero. Then you can restate the problem in terms of the variables P=p^2, Q=q^2, R=r^2, X1=x1*p, Y1=y1*q, etc. Substituting and clearing denominators gives another 12 equations in the new variables; this appears to be a more complicated ideal, but in fact as the solution set is smaller, Magma seems to treat it more efficiently. Perhaps some of the algorithmic commutative algebra people can comment as to the comparative efficiency of the several approaches. I've still got some machines playing with examples, so I'd be willing to experiment with suggestions. This run succeeded, for example: //Magma program to help deduce locations of lines meeting given conditions p:=10000000019; K:=GF(p); //Now, I can't call the ring and the variable both R so let G:=PolynomialRing(K,12,"lex"); a1:=1;a2:=2;a3:=3;a4:=5;a5:=7;a6:=11;a7:=12;a8:=17;a9:=25; a10:=31;a11:=197;a12:=1001; I:=ideal; time J:=EliminationIdeal(I,9); //This took 30192 seconds, about 8.3 hours Groebner(J); Write("Seeme2",J); quit; dave