From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: 3D Geometry problem Date: 27 Dec 1999 08:24:08 GMT Newsgroups: sci.math.num-analysis Keywords: determine locations of points given bipartite distances In an earlier article, Ed McBride asked how to determine the locations of nine points given (1) all the distances from four of them to the other five (2) the premise that the four are planar (3) normalization conditions to remove ambiguity because of invariance under Euclidean motion. I responded, optimistically and without really thinking about the particulars, > I guess this looks to me like 20 quadratic equations in 20 unknowns. If > you have a good estimate of the solution (e.g. if the positions are > moving continuously and you merely need to update them to reflect > new measurements) then a continuation method ought to work well. If > instead you're working ab initio you could probably make an elimination > theory / Groebner basis analysis to diagonalize the system of equations, > but I doubt this would be fast, which was stated as a requirement. When I actually went to try some examples I realized the situation was rather like another one I had once considered, in which the following observation is made: the fact that the points lie in R^3 puts algebraic constraints on the possible interpoint distances. Therefore, the twenty observed distances are not necessarily independent pieces of information. Consequently if the measured distances are true there are actually insufficient data to determine the positions uniquely! To take a specific example, consider the case in which the four points on a plane are near the corners of a 40x40 square, and the other five points are more or less stacked above the center of the square. I picked some values at random for the values a_{i,j} = dist(P_i, P_j)^2 in this ballpark: a15:=999;a16:=1001;a17:=1005; a25:=1099;a26:=1102;a27:=1115;a28:=1131;a29:=1137; a35:=1201;a36:=1207;a37:=1225;a38:=1251;a39:=1253; a45:=1506;a46:=1502;a47:=1523;a48:=1554;a49:=1578; Notice that a18 and a19 are not given; that's because they can be determined from the other data. A few minutes' calculations by Magma show that a18 = 59199/59, a19 = 59441/59. So only 18 of the equations give independent information, and the solution set is 2-dimensional (i.e., NOT a finite set of vectors in R^20). In this particular problem, we may for example choose (x4,y4) at will, solve for x2 from x2^2 - 44/81*x2*x4 + 341/2052*x4^2 + 341/2052*y4^2 = 10153/171, and then compute x3 = 152/71*x2 - 22/71*x4, y3=-22/71*y4. Similar but messier formulas also exist for the coordinates of each of the remaining five points, always in terms of x2, x4, y4. The last two are more or less arbitrary (we must choose point #4 in a certain region if we want the coordinates of all points to be real). While it is perhaps unexpected that this should be the conclusion in the problem at hand, it is clear that this phenomenon must arise in more general problems. If we have a set of n points and a set of m points in R^k and we know all n*m distances between the pairs, we might expect to determine all k*(n+m) coordinates of the points (modulo the action of the Euclidean group, of dimension k*(k+1)/2 ). But if the distances are chosen randomly these equations are nearly certain to be inconsistent except for small n and m. Indeed, if n = k + n' and m = k + m' for positive n' and m' with n'*m' > k*(k-1)/2 , we have k^2 + (n'+m')*k + (n'*m') 'random' equations in (3/2)*k^2 - (1/2)*k + (n'+m')*k unknowns, which will be inconsistent. Here's the specific example I had encountered before: taking k=3 we see that for example n=m=5 will lead to an over-constrained system in general, and that even when the n*m distances are chosen correctly, the generic situation should lead to a unique solution for the positions of the ten points. In brief, this means the following: an arrangement of 25 hinged beams joining each of five points to each of five other points will be rigid in R^3 (even though it contains no triangles). Returning to the original problem in this thread, let me simply note that it will evidently be necessary to collect more data before the positions of the nine points can be determined. Probably the points can be quickly located once sufficient data are provided. dave ============================================================================== [The original poster responded that, in fact, there were _eight_ above-ground points in addition to the four on the ground, and all 32 pairs of distances were known. It was expected that with this extra information, the solution would surely be unique. Not so. --djr] ============================================================================== [A version of this letter was sent by me, around Dec 29 1999, in response to the original poster's attempt to recover positions from distances starting with the four points and the eight points roughly in two squares. The following experiment shows that, in fact, the solution is still not unique. --djr] OK, I ran some numbers. Your description of the data set you ran was a little unclear but the following points make a set consistent with your verbal description. It really doesn't matter, I suppose, just what the pattern is, but what I did was to take (1) P1 = origin, P2 on x-axis, P3, P4 on xy-plane; (2) P1, P2, P3, P4 form a square of diagonal=20, plus random noise; (3) P5 through P8 are the vertices and midpoints of a square of side 30 and height 14, tucked into the first quadrant, again plus random noise. Here are my nominal positions (coordinates in columns): [0 14 15 2 2 13 31 29 30 16 1 0] [ ] P := [0 0 13 16 -1 2 0 15 29 27 28 17] [ ] [0 0 0 0 14 14 15 14 16 13 14 14] The 4*8 distances between them range from 14.18 to 44.69; actually their squares are nice integers; here are the squares of the distances: [201 369 1186 1262 1997 1154 981 485] [ ] [341 201 514 646 1353 902 1149 681] [ ] [561 321 650 396 737 366 617 437] [ ] [485 513 1322 926 1209 486 341 201] I want to stress that I didn't do anything on purpose to make this example 'special'. While the theory supports the claims that I make below, you should really create more examples to test them, since it is possible that I by accident chose an example which is 'degenerate' in a way I cannot perceive. OK, try whatever method you want to take those last 32 numbers and try to recover the 29 unknown coordinates. I used elimination theory on the 32 equations in 29 variables. It goes pretty fast. First I look for relations among x2, x3, and y3 and find the _only_ one to be 3531/392*x2^2 - 214/21*x2*x3 + x3^2 + y3^2 - 39/2 = 0 In particular, this tells me already that there are not unique values for these three variables! Actually I'll let you in on a little number-theorists' secret: you can describe _all_ the solutions (x2,x3,y3) to this last equation parameterically: Take arbitrary rational m and n and compute x2=14*(1-676*m+119626*m^2+156*n-66768*m*n+13482*n^2)/(-119626*m^2+63558*n^2+1), x3=3*(598130*m^2+317790*n^2+5-550836*m*n-2782*m)/(-119626*m^2+63558*n^2+1), y3=-13*(119626*m^2+63558*n^2-1-276060*m*n+642*n)/(-119626*m^2+63558*n^2+1), For example, m=n=0 gives the triple (14,15,13) with which we began. Special bonus: if m,n are rational, so are x2,x3,y3 -- we can do our computations with exact arithmetic. Next I use elimination to find relations among sets of variables {x2, x3, y3, x_i, y_i, z_i} for i=4,5,...,12. This turns out to be nice in every case. The simplest case i=4 leads to the solution {x4 = -107/91*x2+16/13*x3, y4 = 16/13*y3, z4=0} The other 8 are very similar to the case i=5 where I find {x5 = -28/10593*(-214*x2*x3+26073+21*x3^2+21*y3^2)/x2, y5 = 1/21186*(1460088*x3-3813480*x2-1391*x2*x3^2+10593*x2*y3^2+ 1176*x3^3+1176*x3*y3^2)/y3/x2} and determine z5 from z5^2 = 201 - (x5^2 + y5^2). So there are _oodles_ of possible solutions. Pick any x2, x3, y3 satisfying that one quadratic equation (e.g. pick any rational m,n and plug into the parameterization I gave); then use formulas like those shown to determine (x4,y4), (x5,y5), ..., (x12,y12); then compute the z's just so that the 8 points have the right distance from the origin. This last step puts some inequalities on the m's and n's since we must be extracting square roots of _positive_ numbers. There are many parts of the m-n plane where this process will work OK. I sat down and figured out the region containing the origin m=n=0 where all the square roots could be extracted. (It's pretty small in these coordinates.) For your amusement I took a walk around the edge of the acceptable region to find some solutions to the original problem which are markedly different. I will give them below. I should emphasize that the solutions are _exact_: the points match all the 32 interpoint distances on the nose. I did not report the results this way because it's too long to write, but each of the solutions below lists 12 points whose x and y coordinates are rational and whose z coordinates are either rational or square roots of rational numbers. As you look at these solutions you might watch to see how individual points among the 12 move around in space (the solutions are actually snapshots of a continuous loop of solutions). Check out which points come nearly down to the plane z=0 (all but two eventually do) and which go high (point #9 gets as high as z=27). There may be other interesting patterns too; I didn't check. It might be cool to animate this! (I can compute the coordinates essentially instantly.) So I don't know what you are really doing with this computation, but you're going to need some more information to determine positions. You've still got two degrees of freedom, and so need two more _independent_ bits of data. I'm guessing more airborne points won't help at all; maybe another point on the ground would help. Certainly a couple of distances e.g. among the points on the ground would help. dave Note: ts(x,y) was my Maple routine to find the points corresponding to m=x/1000, n=y/1000. So ts(0,0) gives the 12 original points (you would see here the transpose of the matrix P, above). > ts(.28,.12); [ 0 0 0 ] [ 11.81476540 0 0 ] [ 12.87093688 12.08754438 0 ] [ 1.949066294 14.87697769 0 ] [-.01740697290 -1.976504293 14.03898600] [ 13.01713031 1.021068441 14.08941936] [ 34.34637312 -1.504451800 2.015757620] [ 31.97645726 14.66947332 4.930794398] [ 33.16141518 29.70548685 3.860646941] [ 16.57200411 27.84582569 10.19699324] [-1.202364906 29.23343438 11.17857920] [-2.387322840 17.42388262 13.25552730] > ts(.09,.23); [ 0 0 0 ] [13.62215978 0 0 ] [14.24552784 11.07190448 0 ] [1.515692535 13.62695936 0 ] [1.672394027 -3.708762981 13.58116988] [12.97750294 .1706740508 14.16175441] [31.47677204 -1.593417516 13.88070037] [29.42129770 15.95381814 11.91062251] [30.44903486 32.42427645 4.303786008] [16.06071446 29.62161674 4.314310293] [.6446568536 30.30893098 7.871030574] [-.3830803197 17.36090190 13.54445772] > ts(-1.1,.03); [ 0 0 0 ] [31.02197931 0 0 ] [30.87443226 12.56706094 0 ] [1.522907984 15.46715192 0 ] [13.25452500 -2.677248111 4.260271077] [18.21874725 1.359690723 5.935359293] [26.34202003 .8184794538 22.16817702] [25.43943417 16.16549075 18.80191741] [25.89072710 30.73266662 19.54925710] [19.57262605 27.47556318 4.000717073] [12.80323207 27.23693906 8.673315381] [12.35193913 15.77311409 9.145407142] > ts(-1.17, -.33); [ 0 0 0 ] [31.19718890 0 0 ] [31.65090507 17.69640911 0 ] [2.272551136 21.78019582 0 ] [13.35480254 3.095529469 3.614823137] [18.29114476 5.794399138 .9268021472] [26.36879563 5.135228090 21.54799410] [25.47127885 16.06440679 18.84539170] [25.92003722 26.39398214 25.07008929] [19.63741990 24.29471586 13.34685435] [12.90604417 24.35428350 14.87625284] [12.45728579 16.22854512 8.151708655] > ts(-1.03, -1.6); [ 0 0 0 ] [20.24817171 0 0 ] [24.34582849 27.51779183 0 ] [6.155806792 33.86805149 0 ] [6.666983604 12.08893790 3.226284225] [14.27260855 12.77339541 1.460484406] [26.71817665 10.62941284 18.95137513] [25.33533575 17.84897495 17.36475901] [26.02675620 24.39625887 26.91524689] [16.34686990 24.38407953 17.09375646] [5.975563155 25.85578396 16.63643836] [5.284142708 20.72576490 5.245998980] > ts(-1.0,-2.1); [ 0 0 0 ] [16.73330992 0 0 ] [22.29281473 28.31491092 0 ] [7.761880084 34.84912114 0 ] [4.183382176 13.28248999 2.659844620] [13.38658230 13.24133729 3.803472295] [28.44636433 10.00188048 16.63630800] [26.77305521 17.14662378 15.84918950] [27.60970978 23.44537624 26.17285350] [15.89654598 24.33251978 17.58488861] [3.346727619 26.72598574 15.98502739] [2.510073063 21.80459944 1.805263554] > ts(-.8, -2.2); [ 0 0 0 ] [13.89584963 0 0 ] [19.92681488 26.54874092 0 ] [8.186234680 32.67537344 0 ] [1.910449467 12.53873493 6.334848799] [12.99289524 11.90451104 7.646390671] [31.12780650 7.483547364 12.69079124] [29.11281636 15.21093211 13.53039056] [30.12031144 21.87504597 24.72345454] [16.01538045 23.57254072 18.48899439] [.9029543944 26.93023352 15.96706600] [-.1045406749 21.73511588 3.545956697] > ts(-.6, -2.0); [ 0 0 0 ] [12.83605751 0 0 ] [18.56396144 24.87987146 0 ] [7.755005802 30.62138026 0 ] [.9646409068 11.41110307 8.358001831] [12.96209417 10.65867717 9.347551326] [32.59429041 5.817360592 9.474732070] [30.41293528 14.07683222 11.78542164] [31.50361284 21.18107728 23.57719965] [16.23412688 23.08872976 18.90406525] [-.1260366640 26.77481976 16.25094280] [-1.216714233 21.23810690 5.697580337] > ts(-.2, -1.33); [ 0 0 0 ] [11.86330465 0 0 ] [16.23973558 21.24424160 0 ] [6.038206458 26.14675890 0 ] [.03110419968 8.332530088 11.47030840] [13.01231008 8.011909054 11.63997851] [34.25428333 3.259372783 1.421464759] [31.89406408 12.83040574 8.952617740] [33.07417370 21.20139563 21.29788387] [16.55263895 22.72205976 19.07139596] [-1.149005425 26.27455294 17.00963414] [-2.329115052 19.73935464 9.483306465] ============================================================================== From: Ed McBride Subject: Re: Sample set of 12 points (LONG) Date: Thu, 30 Dec 1999 09:19:51 -0700 Newsgroups: [missing] To: Dave Rusin [deletia --djr] > > For various reasons, we are limited to eight upper and four lower > > points. I sort of lied here. We "could" do nearly anything, but the electronics (multiplexing all the signals) limits us to these numbers, and the cost of re-doing the system is not warranted unless we can first solve all this opther stuff and convince ourselves we can sell a whole bunch of systems. > > Distances among upper points is not feasible, but all six > > distances between lower points "could" be obtained. However, if any > > five were known, then their locations are also known, and then each > > upper point is also known from simple trig. So, can we make this thing > > work with one lower distance? Or, if not, two? Or... > > No one distance will suffice. > > Any two distances would give a finite solution set; you'd have to hope > that the various solutions are either sufficiently different that you can > tell which ones are wrong, or sufficiently close that it doesn't matter > which is really the right configuration. > > Any set of three distances would have a unique solution unless you are > deucedly unlucky. There is the little matter of noisy data which would then > conflict and have to be reconciled; I'd have to give that some more thought. Did you answer the above three questions as a result of something that was implicit in the previous work you did, or did this require aditional analysis? > > This has been an interesting question. I was even able to explain the > problem to my teenagers. I told them to imagine there were 8 Mars landers > with little transmitters and 4 Mars rovers with litte receivers about > whose positions we knew nothing except that the rovers were on the ground > and from the transmissions we could determine distances. They thought > that was a pretty cool problem. They also said not to lose the landers > this time :-) Good point. You may have noted that I work in "real" units whenever possible, and try to avoid anything that reminds me of all those people who got so good surrendering to Germans. > > It's also a little like a toy I saw this year consisting of zillions of > little plastic sticks hinged together to make a four-foot soccer-ball sort > of thing except the pattern of sticks was more complicated than the usual > pentagons and hexagons of the soccer ball. One can push in on the sides > and the thing collapses to a one-foot ball of folded sticks. Here all the > distances between hinge points stay constant but there is this one-parameter > family of possible positions for the whole configuration. Yeah, I've been using a similar analogy here. I think of your development of many (How many BTW?) distinct exact solutions as a whole bunch of elastic sticks that are stable at one exact length each. So they deform to get from one solution to another, but lock back to their original lengths at each new solution. Hope you all have a great New Years. Ed ============================================================================== [Actual application calibrating a triangulating device involving 4 roving transmitters and 8 fixed receivers. During the calibration the 8 receivers' locations are completely unknown; road crews position the 4 transmitters more or less in specified nominal positions on the floor. The goal is to determine the positions of all objects, in particular the 8 fixed receivers in the air, without assuming the on-the-floor distances have been measured accurately if at all. Below, we succeed if given at least two distances on the floor sharing a common vertex. --djr] ============================================================================== From: Dave Rusin Subject: Got a nice solution for you Date: Tue, 4 Jan 2000 12:33:10 -0600 (CST) Newsgroups: [missing] To: emcbride@wybron.com First of all I must tell you that I tried some examples last night and discovered that adding the lengths of the two diagonals does NOT seem sufficient information to determine positions. I haven't quite figured out why that happens. But then I put away the keyboard for a little while and found that it's actually quite easy to analyze this whole thing with pencil and paper. You can probably turn this into a fast and robust algorithm -- still requiring at least two additional measurements, of course, but using them efficiently. Here's my analysis. We're trying to locate four points on the ground and let's say N of them in the air. As before I'll set up coordinates so that one of the ground points -- I'll call it u_0 -- is at the origin, so that the positions of all the other points can be thought of as vectors in R^3. Call the ground vectors u_1, u_2, u_3 (so their z-coordinates are zero) and the other points v_j (j=1, 2, ..., N). Now, you start with 4N equations telling you the squares of certain distances. These distances are the lengths of vectors between points, which in turn are differences of the position vectors, that is, our equations have the form D_{i,j} = || u_i - v_j ||^2 for some positive constants D_{i,j} which your instruments will measure very accurately. I'm going to have to assume you begin with at least some additional data. It will be sufficient to have the crew measure two distances from the point we called u_0; that is, they are measuring the lengths of, say, u_1 and u_2, giving two more equations a_1 = || u_1 ||^2 a_2 = || u_2 ||^2 You can have the guys measure the distance from the origin to the remaining ground point too, but I'll show how that distance can be computed from the others. Probably it would be profitable to have them measure all three, then use the redundant measurement to improve accuracy with a least-squares fit somewhere along the way. I'll get to that later, I think. Anyway, you now have 4N+2 quadratic equations in 3N+5 variables. But it makes sense to rewrite these equations by simply subtracting one (from each set of four) from the others. That is, for each j we replace our four equations above with these four: D_{0,j} = || u_0 - v_j ||^2 = ||v_j||^2 (the old i=0 one) D_{i,j}-D_{0,j} = || u_i - v_j ||^2 - || v_j ||^2 (for i=1,2,3) Now, ||v||^2 = < v, v > where the pointy brackets indicate an inner product (dot product) so when we expand this last line we get, after some manipulation, D_{i,j}-D_{0,j}-a_i = -2 < u_i, v_j > Since the z-coordinate of u_i is zero, this last equation involves only the first two coordinates of v_j, and is linear in them. So the strategy is to ignore the first equation D_{0,j}=... until the very end, and then use it to compute the z-coordinate of v_j after its x- and y-coordinates are computed from the other equations. I'm setting aside exactly N equations which I will use to solve (uniquely) for the N remaining (positive) variables z_j. In what follows then, I will have only 3N+2 equations in 2N unknowns x_j, y_j, plus the 5 unknown coordinates of the u_i's. Let's not make any use of the two known values of the a_i just yet; treat them as variables. Those 3N equations may now be simply written in matrix form as A X = B where X is the 2 by N matrix whose columns are the unknowns [x_j, y_j]' , A is the 3 by 2 matrix whose rows are the coordinates of the u_i, and B is the 3 by N matrix whose (i,j) entry is (-1/2)(D_{i,j}-D_{0,j}-a_i). Some elementary linear algebra shows that since A and X have rank at most 2, so must B, so that every 3x3 submatrix of it has determinant zero. Well, any of those 3x3 minors has a determinant which is linear in the a_i; in particular, this is now your equation to determine a_3 if you are given a_1 and a_2. (Depending on the accuracy of your hardware you may find that the different minors give slightly different linear relations among the a_i. It's probably a good idea, from a robustness point of view, to compute many or all of the minors and select an optimal linear relation by averaging or some kind of least-squares fit. This also gives you a chance to fudge data if you _do_ have the guys measure all three a_i's: assume an unknown relative error in each measurement, then determine the errors which make the matrix B as close to singular as possible. I'll leave this part to you...) However you do it, the rank-2 condition and the knowledge of at least two of the a_i are enough to let us treat the matrix B now as known. Also note that for any column vector C, the equation A X = C is only solvable if C lies in the column-space of A, that is, it's in the plane (through the origin) spanned by the two columns of A. Applying this reasoning to each column C of the matrix B, we see _all_ those columns lie in the same plane as the columns of A. Of course, unless you're very unlucky, any two of those columns of B ought to span the same plane. That's handy since the matrix B is now known, and therefore we can actually compute the plane in question. So now you can address the computation of A . Recall its rows contain the five unknown coordinates of the points u_1, u_2, u_3 on the floor. But now you have five pieces of information about those coordinates! (1) || u_i ||^2 = a_i for i=1, 2, 3 (the numbers a_i now known) (2) the x-coordinates of the three vectors give a point in this special plane (3) so do the y-coordinates (note: y-coordinate of u_1 is assumed to be zero). So use (1) to compute the vector u_1, then use (2) and (3) to express the x- and y-coordinates (respectively) of u_3 in terms of those of u_2, plug into the appropriate equation of (1) and end up with just two quadratic equations to solve in the two coordinates of u_2. (This is actually very easy in this problem.) Then work backwards to get the coordinates of u_3, and hence the whole matrix A, and then the matrix X=A\B (which contains the x- and y-coordinates of the vectors v_j). Finally use those long-discarded equations D_{0,j}=||v_j||^2 to compute the z-coordinates of the v_j. Observe that the solutions now _are_ unique at each step (using positivity of z_j at the end) except possibly for the solution of two quadratics in two unknowns. These turn out to be unique too, given appropriate sign conventions. I will do an example for you. Recall the data I sent once before, with these interpoint distance D_{i,j}: [201 369 1186 1262 1997 1154 981 485] [ ] [341 201 514 646 1353 902 1149 681] D := [ ] [561 321 650 396 737 366 617 437] [ ] [485 513 1322 926 1209 486 341 201] From this I compute the matrix B: [ -70+a1/2, 84+a1/2, 336+a1/2, 308+a1/2, 322+a1/2,126+a1/2,-84+a1/2,-98+a1/2] [-180+a2/2, 24+a2/2, 268+a2/2, 433+a2/2, 630+a2/2,394+a2/2,182+a2/2, 24+a2/2] [-142+a3/2,-72+a3/2, -68+a3/2, 168+a3/2, 394+a3/2,334+a3/2,320+a3/2,142+a3/2] The rank-2 condition is expressed by setting the determinant of the first 3 columns to zero: -38304 + 6916 a3 - 8512 a2 + 8132 a1 = 0. Well, the last time I worked with these data I didn't assume I knew any more distances. This time I will assume it to be known that the squared distance from u0 to u1 is 196 and the squared distance from u0 to u2 (across the diagonal) is 394. From this eqaution I then conclude (correctly!) that the squared distance to the fourth ground point is 260. With these data, the matrix B becomes a bunch of scalars: [ 28 182 434 406 420 224 14 0] [ ] [ 17 221 465 630 827 591 379 221] [ ] [-12 58 62 298 524 464 450 272] It does indeed have rank 2, and in fact a row vector which annihilates it on the left is [107, -112, 91]. In other words, the plane containing all those columns is the plane 107x - 112y + 91z = 0. From the assumed matrix equation A X = B we then see A is also annihilated by this vector. Well, here's A, of course: [X1 0 ] [ ] A := [X2 Y2] [ ] [X3 Y3] so now these five coordinates are just about known. Our equations are (1) X1^2 = 196, X2^2+Y2^2=394, X3^2+Y3^2=260 (2) 107 X1 - 112 X2 + 91 X3 = 0 (3) 107 *0 - 112 Y2 + 91 Y3 = 0 So I see X1=14[*], X3 = -214/13+16/13*X2, Y3 = 16/13*Y2. All that's left is X2^2+Y2^2=394 and 45796-6848*X2+256*X2^2+256*Y2^2 = 43940 and in fact you'll never have a Y2 except squared, so we can subtract and rewrite this this way: 146660 - 6848 X2 = 43940 and Y2^2 = 394 - X2^2 whose solution is X2=15, Y2=13[*] [*]Note: I'm assuming you know which are the positive directions for the axes so we use the positive square root. Working back, I get X3=2, Y3=16, so that the equation A X = B reads [14 0] [ ] [x1 y1 x2 y2 x3 y3 x4 y4] [15 13] * [ ] = [ ] [x5 y5 x6 y6 x7 y7 x8 y8] [ 2 16] [ 28 182 434 406 420 224 14 0] [ ] = [ 17 221 465 630 827 591 379 221] [ ] [-12 58 62 298 524 464 450 272] which has the unique solution X = [ 2 13 31 29 30 16 1 0] [ ] [-1 2 0 15 29 27 28 17] Finally using the distances from the origin (the top row of D) we see eg. x_1^2 + y_1^2 + z_1^2 = 201 becomes simply z_1^2 = 201-2^2-(-1)^2=196 so z_1 = 14; likewise I compute all the z_i = [14, 14, 15, 14, 16, 13, 14, 14] Check your old messages: you'll see I have faithfully recovered all the coordinates of the original points. I'm glad you're finding the elimination theory to be interesting. There's a bit of material at index/13PXX.html which you may find useful. When all is said and done I don't think it's really necessary in this computation, now, but it's good to keep in mind for the future. By the way, I think you've gotten the wrong idea about mathematicians. Many of us work on applied problems. I don't personally feel very well qualified to comment on industrial matters, but I do enjoy seeing the connections to the physical world. I have colleagues here who help design airplane wings and paper processing plants and all manner of things. It's cool. In fact, I'm envious of your exposure to such a variety of circumstances. But a few decades of academic work have left me more confident dealing with more theoretical matters, so the closest I seem to get is as intermediary between camps, as I am in the present circumstance. dave ============================================================================== From: Ed McBride Subject: Re: Got a nice solution for you Date: Tue, 04 Jan 2000 12:04:53 -0700 Newsgroups: [missing] To: Dave Rusin Dave, Got it and printed it. Scanned it, but too fast to understand. I'll read it in detail tomorrow. > > I'm glad you're finding the elimination theory to be interesting. > There's a bit of material at index/13PXX.html Right, your web page is high on my list of priorities, I hope tomorrow morning, or tonight if I get my other stuff done. [deletia --djr] > Many of us work on applied problems. I don't personally feel very well > qualified to comment on industrial matters, but I do enjoy seeing the > connections to the physical world. I have colleagues here who help > design airplane wings and paper processing plants and all manner of things. Seriously, I always thought THE most important stuff you folks did was in the area of uniqueness, and as you did here, determining whether a solution exists, stuff like that. It's awfully nice to "know" that there are N linearly independent solutions to an Nth order O.D.E. and exactly one particular solution, and all the other things you've done over the years. Try to understand how valuable your solution was; without it, I'm still trying iterative numerical solutions, and thinking I'm getting stuck at local minima, and never even considering that there are multiple solutions (It is STILL difficult for me to visualize the tinker toy being assembled in many different ways and all the sticks staying the same length). > It's cool. In fact, I'm envious of your exposure to such a variety of > circumstances. But a few decades of academic work have left me more > confident dealing with more theoretical matters, so the closest I seem > to get is as intermediary between camps, as I am in the present circumstance. Well, it seems to me you're doing a great job of it! Ed ============================================================================== From: Ed McBride Subject: Solution Date: Wed, 05 Jan 2000 11:29:24 -0700 Newsgroups: [missing] To: rusin@math.niu.edu Dave, I read what you sent, and almost everything makes sense. Congratulations on finding a very clever solution! My biggest problem is that I do linear algebra by example, never having "learned" everything. So I'm starting the following: 1. Re-write what you sent using subscript notation, and putting in all the rationale to force me to understand rather than mimic. 2. Go through your example carefully, making sure I can get all the answers. 3. Write a "program", probably in Mathematica, and make sure it can do your example. 4. The final solution has to be in C to go into the processor, but I fortunately don't have to write it, merely provide the algorithm. so this step is pretty trivial, especially for ME. I did something very stupid, and erased your message after printing it. So I can't ask or respond cleverly. Anyway, You use the notation X = A \ B. Since our original matrix equation was A X = B, I started to think your equation was X = (A inverse) B. But A isn't square, so it doesn't have an inverse. Is it a 2 by 3 matrix that pre-multiplies A to yield a 2 by 2 Identity matrix? Whatever it is, is it straightforward to calculate it from A? You are correct about knowing directions. I envision the points in a sort-of square, with one diagonal running left-to-right across the stage. Point 1 (0,0,0) will be at the left vertex. Point 2 (x2,0,0) will be at the right vertex. Point 3 (x3,y3,0) will be the vertex such that x3 > 0 and y3 > 0. Point 4 (x4,y4,0) will be such that x4 > 0, y4 < 0. I got very confused in your linear algebra tutorial, second paragraph. (1) What is a plane (through the origin) spanned by the two columns of A? (2) How can A X = C be valid for a column vector C? A is 3 by 2, X is 2 by 8, so why doesn't C have to be 3 by 8? In your example, I follow where you calculate B(numbers plus a1,a2,a3). Then use the rank-2 condition to get an equation involving a1,a2,a3 and use the two known ones to calculate the unknown one (I don't see why all the higher-order terms in the a's went away, but I haven't worked through the determinant yet.) Then you use the a's to get B(numbers only ). Then you somehow determined a row vector [107,-112,91] that "annihilates it on the left". I understand that if you multiply this row vector times B you get a 1 by 8 (row vector) with all zeroes. And if you multiply it by A you get a 1 by 2 with all zeroes which you use, along with the three distances, to find A. But this row vector is obviously not unique. I would have used the first two columns of B, set the row vector equal to [1,y,z] and multiplied to give me two simultaneous equations for y and z. You obviously have a more clever way, but I haven't been able to figure it out. Trade secret? Time to get to work. [deletia --djr] Thanks again, Ed ============================================================================== From: Dave Rusin Subject: Re: Solution Date: Thu, 6 Jan 2000 15:29:47 -0600 (CST) Newsgroups: [missing] To: emcbride@wybron.com > So I'm starting the following Let me know if anything is unclear. I hammered out the example in Maple; my Mathematica syntax is pretty rusty, but perhaps you could make the translations. >erased your message I keep copies. If you want me to resend it just remind me which you want. By the way, I will probably throw this correspondence into the morass at my web site in case someone else has a similar problem some day. If you want me to remove all traces to your name, let me know; otherwise I'll just strip the letters to the mathematical content and retain some of the headers. You may have already seen how I do this with other entries at the website. > You use the notation X = A \ B I probably shouldn't do that; it's supposed to mean A^(-1) B, I guess. What I meant was the solution to the equation A X = B. In fact (assuming the first two rows of A are linearly independent) you can just drop the last row from the whole equation -- the other steps are supposed to guarantee that the same linear relation holds among the rows of A as among the rows of B. If we refer to these depeditated matrices as A' and B' then the solution to A X = B is X = (A')^(-1) (B'). > I envision the points in a sort-of square, You know, if you intend to ask the road crew to measure all _three_ distances from the vertex called (0,0), it might make sense to ask them to spread out the beltpacks into a Y shape. Attach three of them to the "origin" one with canvas straps, and ask them just to pull tight on those other three. The angles don't matter at all (they could even have the four vertices at the corners of a square as you originally proposed) as long as those 2 or three distances are accurate. By picking a "Y" as the nominal shape, you get a good spread of the points on the floor, which I imagine (I haven't run experiments) would give the smallest error in the computed locations for a given error in the measurements caused by the road crew. > I got very confused in your linear algebra tutorial, second paragraph. > What is a plane (through the origin) spanned by the two columns of A? Take the numbers in the columns to be coordinates of two points in 3-space; those two points lie on a unique plane through the origin. > (2) How can A X = C be valid for a column vector C? My bad. This X is not the same X as in the previous discussion. I just mean "the problem A*(an unknown vector) = (a known vector) is solvable iff the known vector is in the span of the columns of A". > I would have used the first two columns of B, set > the row vector equal to [1,y,z] and multiplied to give me two > simultaneous equations for y and z. You obviously have a more clever > way, but I haven't been able to figure it out. Trade secret? If the magicians explain all their tricks no one will come to watch :-) Actually I did just exactly what you did, and then cleared denominators at the end. Strictly speaking that's unwise, since there is always the possibility that the first coordinate of the vector you're looking for will be a 0. Numerical analysis types will tell you there are more stable methods of solving this kind of equation using matrix factorizations and so on. I'm sort of hoping not to have to get into these details on the assumption that you have a well-prepared library of function calls at your disposal (e.g. LAPACK or something) or are willing to get the routines from netlib or GAMS . See www.math-atlas.org/index/65-XX.html [deletia --djr] dave