Math Quiz 11

*There are nine tiny dots, labeled 1 thru 9, on a gym floor.

Jane measures the distances between pairs as follows:

*

*2	4	47.8017
3	5	69.2026
5	9	148.492
7	8	86.764
5	6	63.0714
2	8	189.528
6	7	65.192
4	9	147.085
2	3	90.5207
6	8	86.0349
3	9	171.956
4	7	88.8144

What is the distance from point 8 to point 9?

I plugged all the points and dimensions into Solidworks, nothing is defined so my answer is:

Unsolvable!

(99% sure I did something wrong)





8.06 units?

Also, no information is given about point number 1. Is that a typo?

157.674

294.325?

I’m getting a whole range of values. I’m using SolidWorks in a similar fashion to Brian. Here’s the link to my solution if anyone wants to do a sanity check for me.

I think you have two different points for 2.

Also, your 47.80 dimension is the horizontal distance, not the linear distance between points.

EDIT - Ignore me.

That’s the distance to the top right point, not the one the number is closest to.

Woops! Thanks for catching that. You’re right.

174.7256.

Link to my CAD (I found this cool, CAD package online in order to do it… seems to work pretty well, at least for this stuff, and you can have a public free account!)

Anyone see any mistakes? I even labeled my points :slight_smile:

Edit: Out of curiosity Ether, is there a purely mathematical way to arrive at the answer, one that can be done by hand on a single sheet of paper? :slight_smile:





Looking at the topology, we have two triangles: 3-5-9 and 8-6-7.

Points 6 and 5 are connected to each other, points 3 and 8 are connected to point 2, 7 and 9 are connected to point 4, and points 2 and 4 are connected. That is:


          9 ---- 4 ---- 7
          | \    |    / |
          |  3 - 2 - 8  |
          | /         \ |
          5 ----------- 6

Angles within of the two triangles are fixed. But, even given a solution to the mirror ambiguity, there are two unknowns (e.g. angle 9-3-2 and angle 2-8-7) and only one constraint (distance 5-6). Unless this is at some limiting value, there does not appear to be enough information to constrain the distance between 8 and 9.

Gus, you continue to amaze me. You are a true polymath.

I figured you were lurking in the background, waiting to pounce on this.

Here’s another way to analyze this:

Jane made 12 distance measurements.

Pick a Cartesian coordinate system with point2 at the origin and point3 on the +X axis.

So the coordinates of point2 are [0,0].

Since Jane measured the distance from 2->3, and point3 lies on the +X axis, the coordinates of point3 are [146,0].

That leaves 6 points (4 thru 9) whose coordinates are unknown. Since there are 2 scalar values per point, you have 12 unknowns.

But you only have 11 measurements left, because you already used the distance from 2->3.

So you have an underdetermined system of nonlinear equations.

There is no unique solution.

Nice work Jon. You found a valid (but not unique) answer.

Edit: Out of curiosity Ether, is there a purely mathematical way to arrive at the answer, one that can be done by hand on a single sheet of paper? :slight_smile:

What say you, Gus, if Jane had measured the distance from, say, point5 to point8?

I knew I should have posted my musings last night that this wasn’t fully constrained! I had gotten nowhere trying to figure it out by hand, and resolved to give CAD a try this morning. When it came back with an answer, I figured why not :slight_smile:

Adding that to the existing measurements should almost do it. You would only need to determine angle 9-5-8 to get distance 9-8. Measuring 5 to 8 would make triangle 5-8-6, fixing those angles and constraining the orientation of segment 8-7. Excepting edge cases, I would expect two solutions, based on alternate mirror-image solutions of the two fixed shapes (9-3-5 and 5-8-7-6).

Edit - or possibly as many as four. I forgot to consider folding the polygon 5-8-7-6 over segment 8-6.

Edit2 - to clarify, by “edge cases” I mean singularity in the system of equations.

Edit3 - Perhaps even more, due to which way the angles at points 2 and 4 bend. Let’s go with this: With the length of 5-8 determined, and excluding singularity cases, there would be a (fairly small) finite number of solutions. This arises from the nonlinear nature of the system of equations. For example, the single-unknown equation x5 - 5x3 + 4x = 0 has exactly five real solutions. This set of equations appears to be second order (to simplify, square all of the measured lengths to eliminate those square roots), but the cross terms among the different unknowns increases the number of possible solutions.

Edit4 - I think I have a way to find the solutions when the length of segment 5-8 is given, for all 16 possibilities of the four remaining ambiguities* in a not-too-complex excel spreadsheet, if you don’t mind looking for crossing points on graphs. This is stretching Jon’s question, but not totally breaking it. I’m going to work this up with a 5-8 distance of 55.17 (to commemorate the date of 5 May 2017), though this will be adjustable if this turns out not to be an interesting value. If I have enough energy left, I will generate all the plots in excel as well**. Ether, if you have a different 5-8 distance in mind for 5-8, please let me know.

  • At a geometric level, these ambiguities arise from the law of cosines: c2 = a2 + b2 + 2abcosγ. This equation is ambiguous in that while a and b are always positive, γ may be either positive or negative, and cosγ = cos(-γ).

** As it turns out, the graph of the initial set of distances Ether gave is a “double-down” on the classic Bridges of Konigsberg problem - every one of the eight vertices has three measurements! This will make drawing lines using excel scatter plot more interesting.

Letting matlab do the work. Set up a system of equations. x(1) = point2.x, x(2) = point2.y, x(3) = point3.x, etc. This is a set of (xsrc-xdst)^2 + (ysrc-ydst)^2 - distance^2 = 0 equations derived from the list given in the OP.


function F = distEQ(x)

F(1) = (x(1) - x(5))^2 + (x(2) - x(6))^2 - 47.8017^2;
F(2) = (x(3) - x(7))^2 + (x(4) - x(8))^2 - 69.2026^2;
F(3) = (x(7) - x(15))^2 + (x(8) - x(16))^2 - 148.492^2;
F(4) = (x(11) - x(13))^2 + (x(12) - x(14))^2 - 86.764^2;
F(5) = (x(7) - x(9))^2 + (x(8) - x(10))^2 - 63.0714^2;
F(6) = (x(1) - x(13))^2 + (x(2) - x(14))^2 - 189.528^2;
F(7) = (x(9) - x(11))^2 + (x(10) - x(12))^2 - 65.192^2;
F(8) = (x(5) - x(15))^2 + (x(6) - x(16))^2 - 147.085^2;
F(9) = (x(1) - x(3))^2 + (x(2) - x(4))^2 - 90.5207^2;
F(10) = (x(9) - x(13))^2 + (x(10) - x(14))^2 - 86.0349^2;
F(11) = (x(3) - x(15))^2 + (x(4) - x(16))^2 - 171.956^2;
F(12) = (x(5) - x(11))^2 + (x(6) - x(12))^2 - 88.8144^2;
F(13) = x(1) - 0;
F(14) = x(2) - 0;

Save as distEQ.m


>> fun = @distEQ;
>> x0(1:16) = 10;
>> x = fsolve(fun, x0)
x =

 Columns 1 through 7:

   8.7244e-20  -4.0763e-20   8.9553e+01  -1.3199e+01   3.9964e+01   2.6228e+01   3.3832e+01

 Columns 8 through 14:

   2.7839e+01   8.8708e+01   5.8929e+01   5.3763e+01   1.1396e+02   1.3930e+02   1.2852e+02

 Columns 15 and 16:

   1.0523e+02   1.5804e+02

# Convert to x,y coords for point2, 3, 4, etc.
>> xx = reshape(x,2,8)'
xx =

   8.7244e-20  -4.0763e-20
   8.9553e+01  -1.3199e+01
   3.9964e+01   2.6228e+01
   3.3832e+01   2.7839e+01
   8.8708e+01   5.8929e+01
   5.3763e+01   1.1396e+02
   1.3930e+02   1.2852e+02
   1.0523e+02   1.5804e+02

# Sanity check pt2 -> pt4 matches the initial conditions
>> sqrt(sum((xx(1,:) - xx(3,:)).^2))
ans =  47.802

# see what this run gets for 8->9 (remember index - 1)
>> sqrt(sum((xx(7,:) - xx(8,:)).^2))
ans =  45.081

Depending on initial conditions and arbitrary values for x&y of point 2, I also get 282.56, 21.878, 290.81, and probably more (out of battery).

I have attached a spreadsheet which goes through the calculations to solve this problem. I haven’t verified everything on it yet, but I have fixed a lot of problems along the way; I’m mostly posting to show that the problem IS soluble and as a demo of the sorts of ambiguities and multiple roots that make result in multiple solutions to the system of twelve equations in twelve unknowns.

The cells highlighted in yellow are intended to be set as you investigate different values of distance 8-9, and the different ambiguities, or if you want to zoom in to a particular segment of angle 8-5-9; see the notes in the spreadsheet for details. The top graph is a layout of the eight points based on all of the constraints EXCEPT the distance 2-4, and also based on the four ambiguity states and the initial angle 8-5-9. The second plot spans a range of angles 8-5-9. By default, I have it set for the range from 0 to 2pi.

Essentially, you enter the value for distance 8-9, then try each of the 16 ambiguity states, and look for places where the actual distance between points 2 and 4 (red curve) crosses the constraint distance (green line), then trace up that angle to a value for distance 8-9 (blue curve). Ideally, you would use Newton’s method or similar to determine where a crossing occurs, and zoom in on it to find more precisely where the crossing occurs. With the assumed distance 8-9 of 55.17, I found two solutions for false-false-false-true, (approx 190 and 186), two for false-true-true-false (127, 183), and a near miss on true-true-true-false (109).

I don’t think I’ve used anything more complex than the law of cosines to do any of this. Does this answer your question, Jon Stratis?

MQ11.xlsx (58.9 KB)


MQ11.xlsx (58.9 KB)

***Math Quiz 11, Part B:
**
Given three points p1, p2, p3 with coordinates (1,1), (1.5,0.5), and (2.0,0.75) respectively…

… find the coordinates of the point p4 whose distance from points p1, p2, p3 is 1.477601434758372, 1.909792135285932, 2.416879392936271 respectively.

This is an overdetermined trilateration problem (3 constraints, 2 unknowns), which happens frequently due to measurement noise in localization systems (like GPS). As such, the solution depends on what properties you want your residual to have. For one such choice of properties, I happen to know a neat trick that solves this problem elegantly for the particular case where (# constraints) = (# unknowns + 1).

Solution here.

This method adds a free parameter to the distance measurements representing measurement error (assuming it is uniform across all measurements), which lets us solve the system of equations efficiently to find the point representing the center of the three circle-circle intersections (obtained by leaving out one constraint at a time). “h” represents the radius^2 of the circle joining those intersections (which can be imaginary, as in this case, depending on whether or not all three circles overlap or not). The fact that “h” is small in magnitude shows that the solution is very close.

It would also be reasonable to want a (perhaps weighted by distance) least squares solution, but this would require whipping out a non-linear least squares solver.

Gee, that’s some nice math :slight_smile:

For part B… Is the system actually solvable? You can define each circle with the simple equation (x+a)^2 + (y+b)^2 = r^2. That leaves you with 3 equations but only 2 unknowns, which makes it really easy for there to be no solution. Of course, there’s no guarantee that the circles even intersect, but we should assume they do, right? Two circles can have 2, 1, or no intersections in common, likewise three circles can have 2, 1, or 0 common intersections!

Plotting it out, it initially looks like there’s an intersection point (near -0.409, 0.555) … but zoom in and the circles just miss having a common intersection. Plug the system of equations into Wolfram Alpha, and it comes back with no solution, supporting this finding.

So, lets simplify it down to pairs of circles, see how close we actually get.

p1 + p2:
x=-0.409
y=0.5550000000000005

p1 + p3:
x=-0.4089999999999995
y=0.5549999999999989

p2 + p3:
x=-0.4089999999999999
y=-0.5550000000000041

Given how close we are… Is this just a rounding issue with your numbers Ether, or is there intentionally no solution?