OT:Math problem: Grids and conical sections.

BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 24, 2005 at 08:32 UTC
It is sometimes not possible. For instance if all 3 corners have the same height, then you know that the peak must be in the middle, but have no way of figuring out how high that peak is. That said, you have 4 measurements, and you need to figure out 4 variables - the x-coordinate of the peak, the y-coordinate of the peak, the height of the peak, and the slope of the mountain. That means that normally (barring degenerate cases, such as the peak being in the middle) there should be a unique answer. (Or a finite number of them - however a glance at this situation suggests that it will normally be unique.) But that doesn't make it easy to find. I would have to resort in this case to numerical approximations. You can use brute force guessing to come up with a good combination. Or you can try to be clever. If I wanted an easy answer to code, I'd use brute force. If I wanted to be clever, I'd use Newton's method. To refresh your memory, Newton's method works like this. For `x` near `x₀`, `f(x)` is approximately f(x₀) + f'(x₀)(x - x₀) Now suppose that we want `k = f(x)`. Then if `x` is close to `x₀` then we expect the above approximation to be close to `k`. Which means that `x - x₀` is going to be close to: x₀ + (f'(x₀))(-1) (k - f(x₀)) So Newton's method starts with finding one approximation `x₀`, using the above to find a hopefully better approximation `x₁`, which is used to improve to `x₂` and so on. If you start off a long ways away from an approximation, you can still use Newton's method. What you do is check how good an approximation you have. If in a single step your approximation gets worse, then that is because you are travelling farther than the tangent line approximation is good for. But you know that if you just go a short distance in that direction, you should get better. So try travelling in that direction half the distance, 1/4, 1/8 and so on until you find a fraction that is an actual improvement. After improving a few times, then you should get close enough to a real answer that Newton's method just works for you. Now I see you objecting that you can do this for functions of one variable, and here you have functions of many. Well while it seems more complex, this works for functions of many variables as well! All that you have to remember is that `x` is a vector and `f'(x)` is a matrix. Which matrix? It is a mess of partial derivatives. I'm too lazy to type in what mess of which partial derivatives, but it can be found written in lots of places. Also it is trivial to figure out the terms by remembering two facts. The first is that the tangent approximation has to hold in every output dimensions for changes in any one input dimension. The second is the rule for matrix multiplication. When you write those two down, it is easy to see that only one set of partial derivatives can possibly work. To figure out the answer, you'll also need to invert lots of matrices. If you don't want to use PDL, then remember that the fastest way to do invert M is to write `[M \| I]` (where I is the identity matrix) and then apply row operations (multiply row by scalar, swap rows, add multiple of one row to another) to turn that into `[I \| N]`. When you have done so, then N is the inverse of M. (This requires an average of O(n**3) operations. The well-known formula is exponential in the dimension.) Of course Cramer's rule may be faster for you to program, and it isn't THAT much slower in 4 dimensions...	[reply] [d/l] [select]
Re^2: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 24, 2005 at 09:33 UTC
If you take 4 vertical sections through the mountain along the axes between the peak and each corner of the grid, you end up with 4 similar triangles. Whilst the angles aren't known, the proportion between the sides is fixed by the spot heights at the corners. If you lay any two of these sections together so that the tip of the mountain and the axis through it are co-incident, and with the slopes running in opposite directions (like the sails of childs yacht): `.\|. . \| . . \| . ------\| . \|--------` [download] Then all the dimensions of the two triangles will be proportional in the same ratio as the spot heights? And the difference between the two spot heights is known. With this, I think you can form a pair of simultaneous equations that will solve the height; in height units. Using two such pairings, with one "sail" in common, and knowing the ratio between the sides of the grid, assume 1:1, and their absolute lengths in grid units, it should be possible to to solve the two sets of simultaneous equations in concert without recourse to iteration, and find the ratio between the grid coordinates and the heights. I think! Constructing the two sets of simultaneous equations is eluding me. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^3: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 24, 2005 at 19:17 UTC
Yes, you can create a set of simultaneous equations whose solution tells you the answer. Unfortunately it is a set of simultaneous nonlinear equations. Which tells me that you are extremely unlikely to find an analytical solution - you must go to numerical methods. You can get an idea of the difficulties if you look at a few special cases. As everyone has noted, we know that we can find the peak if it is in the middle but we can't find the height or slope. (I am assuming that the slope is positive, if you allow any slope then the same results could be achieved by having the slope be 0 and the position unknowable.) A more interesting special case is where points 1 and 2 are at the same height, but 3 is not. From the fact that 1 and 2 are at the same height, we know that the answer must lie along the line bisecting them. Because it is on that line we know that points 3 and 4 are also at the same height. By assuming that the slope is positive we can figure out which half of that line the peak is on. But we can't find where it is! The problem is that we need to find 4 variables from 4 data points, but 2 pairs of data points are giving us redundant information, so we wind up with 3 pieces of useful information which is not enough to nail down 4 variables. Now let's go for a more promising case. For ease of reference, let's say that points 1, 2, 3 and 4 are at (1,0), (0,1), (-1,0) and (0,-1) respectively. Let's suppose that the height at points 2 and 4 are the same, and 1 is higher than 2. From the symmetry of points 2 and 4, the peak must be on the x-axis. Since the slope is positive, it must be closer to point 1 and point 3. Can we find it? Well let's label the slope S, the height H, and the location of the peak (x,y). Then in general we have: `h(u,v) = H - Ssqrt((x-u)2 + (y-v)2)` [download] In this case we know that y is 0. And by the assumption that the peak is in the box we know that 0<x<1. So we have `h1 = h(1,0) = H - S(1 - x) h2 = h(0,1) = H - Ssqrt(1 + xx) h3 = h(-1,0) = H - S(1 + x)` [download] Well let's try to solve this for x. First subtract h3 from everything to get rid of H. `-h3 + h1 = S(1 + x) - S(1 - x) = 2Sx -h3 + h2 = S(1 + x) - Ssqrt(1 + xx) -h3 + h3 = 0` [download] Now let's get rid of S by multiplying by 2 and dividing by (h1-h3)/2. `2 * (-h3 + h1) / (h1 - h3) = 2 2 * (-h3 + h2) / (h1 - h3) = (1 + x - sqrt(1 + xx)) / x = 1/x + 1 - sqrt(1/x2 + 1)` [download] And for the last expression, its derivative is: `-1/x2 + 1/(x3 sqrt(1 + 1/x2))` [download] This is a complicated derivative, but if you note that that for 0 < x, `sqrt(1 + 1/x2) > 1/x` you'll see that the second term is slightly less than the first term, so for 0 < x < 1 this complex expression is monotone decreasing. Therefore it can be uniquely solved for x. And once you have x, then H and S are easy to find. But good luck finding an analytical solution for x! So we have 2 degenerate cases that we can't solve. And 1 that we can't solve analytically but can numerically. What about the general case? Well as I've been saying, we have 4 data points and 4 variables to solve, so generally it should be solvable. But we probably can't find an analytic solution. So I'd expect from general principles that the general case, excepting the known degenerate ones, can be solved numerically. And the odds against an analytical solution are so high that I won't waste time looking. Incidentally if you move just one point, for example make the first point be (2,0), then there are no degenerate cases and I'd be willing to bet that you can always find the answer numerically. But again, a simple analytical solution is unlikely to exist. If you want to enjoy looking, go ahead. I think that there will be unlimited fun. (Unlimited because you'll never find an answer....) But if you actually need an answer, go with a numerical approach.	[reply] [d/l] [select]
Re^4: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 25, 2005 at 07:18 UTC
Re: OT:Math problem: Grids and conical sections. by QM (Parson) on Nov 24, 2005 at 19:01 UTC
After playing with the similar triangle idea, it's a messy way to go. I assume you've got stuff like this floating around, but just for obviousness, I'll post something here to draw fire^Wcomments. Assuming that the slope is uniform for each vertical cross-section: `\| Zp (peak) \|\ \| \ \| \ \| a \ \| \ \|-----\ (Xa,Ya) \| \ \| b \ \| \ \|---------\ (Xb,Yb) \| \ \| \ \| c \ \| \ \|--------------\ (Xc,Yc) \| \ \| \ \| d \ \| \ \|-------------------\ (Xd,Yd) (Xp,Yp)` [download] The height of each triangle is Hi = Zp-Zi. The base of each triangle is Bi = sqrt((Xp-Xi)2 + (Yp-Yi)2). The slope M of the hypotenuse is Mi = Hi/Bi, and since they're all the same, M = Hi/Bi, and: `Ha Hb Hc Hd -- = -- = -- = -- Ba Bb Bc Bd` [download] Here's where I go wrong -- setting up the system of equations, and solving for Xp, Yp, and Zp. But since you need 3 equations for 3 unknowns, you may only need 3 points, not 4: `Ha Hb -- = -- Ba Bb Ha Hc -- = -- Ba Bc Hb Hc -- = -- Bb Bc` [download] (But I'm fuzzy on the independence of those.) But multiplying all of that out, and solving appropriately, is not something I'm good at. Now if I had a symbolic solver handy, it should pop out straight away (if I've done it right, which is debatable). -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l] [select]
Re: OT:Math problem: Grids and conical sections. by ikegami (Patriarch) on Nov 24, 2005 at 08:32 UTC
I think four points is sufficient to find the location of the peak (but I've failed to figure out how in my tired state), and I'm pretty sure a fifth point is necessary to find the height of the peak (since we don't know the radius of the mountain). Of course, the above is rather useless without being able to back it up. The purpose of this post is really to provide the drawing I've been using (in part) while trying to figure out the solution. ABCD is the grid you presented, and P is the peak the mountain. Update: Struck out what I realize I really do not know. There is definitely at least one case where the four points is insufficient to determine the height (when they are all at the same height), but that's all I know.	[reply]
Re^2: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 24, 2005 at 09:28 UTC
Thanks for the online sketch. I've a about 20 sheets of paper covered with similar sketches, but no way to display them. In the case of the 4 heights being equal, the peak will be centered, and a fifth spot reading there will determine the height. More generally, if the x & y can be calculated, then a fifth reading will retrieve the height directly. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re: OT:Math problem: Grids and conical sections. by johnnywang (Priest) on Nov 24, 2005 at 08:15 UTC
Are you assuming the four corner points are on the surface of the cone? If yes, then to determine the surface of the cone, you need four parameters: (x,y,z) of the tip, and the slop k. You are given four points, which would count as four conditions in generic position. But since you don't know the relative units of the xy and z, you have more variables, can you assume the xy are in the same unit and are proportional to the z? then you have only one additional variable, so another point should be enough.	[reply]
Re^2: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 24, 2005 at 08:33 UTC
Are you assuming the four corner points are on the surface of the cone? Yes. They are point on the surface of the cone. can you assume the xy are in the same unit and are proportional to the z? I need the x and y in the same units as the grid. Whilst the z values I have are proportional to the units of the grid, the ratio is unknown. However, once the x & y have been determined in any units including the same units as the z components I have, the ratio between them and the grid will become known through pythagoras or other means, so conversion will be trivial. The most promising stuff I've turned up is trilinear coordinates, but I'm unsure how to apply them, or even if they are applicable. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^2: OT:Math problem: Grids and conical sections. by QM (Parson) on Nov 24, 2005 at 18:42 UTC
Are you assuming the four corner points are on the surface of the cone? If yes, then to determine the surface of the cone, you need four parameters: (x,y,z) of the tip, and the slop k Thinking out loud here... If you have a point on the surface (x1, y1, z1) and the peak (xp, yp, zp), doesn't that give you the slope k of the cone? I don't think k and z are independent, though it may be easier to find one or the other. -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]
Re: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 24, 2005 at 19:42 UTC
Finding the x and y coordinates of the peak is simple. Since there is no grid, let's arbitrarily choose to make (0,0) be the center of your rectangle and (1,1) be the top right corner. For finding the location of the peak, the height of the peak is irrelevant, so take the height of the top right corner and subtract it from all the heights (effectively lowering the height of the whole landscape). Let: a=adjusted height of top left corner b=adjusted height of bottom left corner c=adjusted height of bottom right corner 0=adjusted height of top right corner ;-) Recognize that the equation for the cone is (x-x')^2+(y-y')^2=m(z-z')^2, but we'll set m=1 because it only effects the slope and thus the height of the peak, which we're ignoring for now. Plug in the above 4 points to get 4 equations. Take the fourth equation and subtract it from the other three to get three new equations that have no ^2 terms: `4x -a^2+2az=0 4x+4y-b^2+2bz=0 4y-c^2+2cz=0` [download] These can be solved straightforwardly. The z value in the solution is irrelevant because I've taken so many shortcuts by procrastinating dealing with z. But for the others, we get: x= a(c-b)(a-b-c) / (4(a+c-b)) ; when (b!=c; a+c != b) y= c(b-a)(b+a-c) / (4(a+c-b)) ; when (b!=c; a+c != b ; a!=0) For the rest, use the similar triangles thing that everyone else recommended: Using the x,y found above, compute the distance between each corner of the rectangle and the computed x,y (remembering that the corners are located at (+/-1, +/-1)). Choose any two of those corners such that their x,y distance to the peak is not equal. Denote their heights h1 and h2 and their x,y distances to the peak as w1 and w2. h=(h1w2 - h2w1) / (w2-w1) (when w2!=w1). Update:The above is based on the incorrect assumption of slope==1. Please discard.	[reply] [d/l]
Re^2: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 24, 2005 at 20:21 UTC
~~I don't recognize your equation for the cone because you've introduced a variable z without explaining what it is. You also are missing necessary square roots.~~ You can't just set the slope at 1 because the slope has a complex effect on the observed heights. Doing that massively simplifies the answer. Those two math errors are significant enough that I see no reason to analyze farther. Update: BrowserUk pointed out where the equation came from. Indeed it did not need square roots. However the slope definitely matters.	[reply]
Re^3: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 24, 2005 at 21:52 UTC
I don't recognize your equation for the cone because you've introduced a variable z Isn't jeffguy's cone equation a reordering of equation 5 on this Wolfram page? Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^4: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 25, 2005 at 02:07 UTC
Re^3: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 25, 2005 at 02:05 UTC
You're right. At first glance, this looked like a term that wouldn't matter because of symmetry. For what it's worth, Z was the term representing the adjusted height of the peak (after subtracting the top-left corner off). Oh well -- back to math!	[reply]
Re^2: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 24, 2005 at 23:47 UTC
Could you post your 4 (missing) equations, and their reduction to the 3 you posted? Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^3: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 25, 2005 at 17:08 UTC
The four equations are the immediate offspring of plugging in values for x and y and z into that first equation I posted: (x-x')^2+(y-y')^2=m(z-z')^2. So for the equation for the top left corner (x'=-1, y'=1, z'=whatever height value was given), we plug those values into the above equation. Alas, I saw symmetry where there was none, and so I set m=1 which allowed much cancelling out. But even without m==1, when you multiply out the squares and then subtract any two equations, all the squares cancel out.	[reply]
Re^4: OT:Math problem: Grids and conical sections. by tilly (Archbishop) on Nov 26, 2005 at 00:54 UTC
Re^5: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 26, 2005 at 01:16 UTC
Some notes below your chosen depth have not been shown here
Re^5: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 28, 2005 at 11:27 UTC
Some notes below your chosen depth have not been shown here
Re: OT:Math problem: Grids and conical sections. by ivancho (Hermit) on Nov 24, 2005 at 20:39 UTC
No one seems to be using that the grid is, in a sense, nice - people seem to solve for generic 4 points, or wrongly assume that a square will project into a square again The 4 points are in one plane, and on a cone - ie, they lie on a conic section. Since we only have a half of the full double cone, then a square(or even a rectangle) can only be inscribed in an ellipse, and not in a parabola or a half of a hyperbola. The only way to inscribe a rectangle in an ellipse is if their centres concide and the axes of that ellipse are parallel to the sides of the rectangle. But the cone vertex will always project on the major ellipse axis in the plane of the ellipse. Therefore, it would project somewhere on one of the 2 lines through the rectangle centre parallel to the sides - it can't go anywhere else. Now follows a question - the height which we have measured at the 4 points - is it along the cone axis (ie, is the cone straight up), or is it in a random other direction? If the former, then the heights of 2 of the grid points will always be equal to the heights of the other 2. Once you find those matching pairs, then you know on which of the 2 lines to look for the cone vertex. I think if you sample 2 more points on that line, you should have 2 lines which intersect in the cone vertex. If the height is in a random direction, then things become hairy.. let me work a bit more on that case.. update: the section is, indeed, conic, not conical... What a giant load of crap... For some reason I decided that the grid points themselves lie on the cone.. Whereas they clearly don't..	[reply]
Re: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 25, 2005 at 08:39 UTC
Okay, so this problem is really kicking my butt (read: ~6 hours). We're given four values and there are only TWO degrees of freedom, so the problem is overspecified and should be easy to solve (darned non-linearities). Why do I say there are only two degrees of freedom? If you're given the slope and height, its easy to compute (based on the heights measured) how far each corner of the grid is horizontally from the peak. From that, it's not hard to get the x,y coordinates of the peak. And given the x,y coordinates, it's easy to get the height of the peak and its slope. So there's definitely only two degrees of freedom. Yet the solution continues to elude me!!!	[reply]
Re^2: OT:Math problem: Grids and conical sections. by BrowserUk (Patriarch) on Nov 25, 2005 at 08:50 UTC
That was my gut reaction when I first encountered the problem, but a combination of tilly's analysis, and my own research and sketches, lead me to have doubts. The most illustrative example is the case of all four corners being the same height. Yes, it fixes the x,y of the center, but you could poke a cone of any slope from flat to infinitely pointy into the 4 points and it would touch all four points if it has sufficient base diameter. There appears to me to be no way to fix the height in that case without a 5th reading. In the non-degenerate cases with 3 or 4 different heights, I am not yet convinced either way that there is a unique solution. Or if there are multiple solutions, that one of them will be obviously correct. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^3: OT:Math problem: Grids and conical sections. by jeffguy (Sexton) on Nov 25, 2005 at 17:18 UTC
A solution is obviously correct if it gives an x, y, and z of the peak such that when you use any of the four measured heights to find the slope, that slope finishes the equation: (x-x')^2+(y-y')^2=m^2(z-z')^2 (or maybe it's 1/m^2 instead of m^2 -- irrelavent details) and the other three measurements all fit into that equation with the given x, y, z, and m. So, when given a solution, it will be clear that it is a solution. Is it clear that there's only one solution for the non-degenerate case? Not yet. But the goal is the same as for the colored points last week that we wanted to separate with (n-1)-dimensional hyperplanes -- can A solution (or even ALL solutions) be found? How?	[reply]