Re: OT:Math problem: Grids and conical sections.

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...

Comment on Re: OT:Math problem: Grids and conical sections. Select or Download Code

Replies are listed 'Best First'.
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
Geez, I was bein silly when I said that this special case cannot readily be solved. In fact in the special case we have: `2 * (-h3 + h2) / (h1 - h3) = 1/x + 1 - sqrt(1/x2 + 1)` [download] Let's declare that value to be a constant K. Then: `K - 1 - 1/x = - sqrt(1/x2 + 1) K2 - 2K - 2K/x + 1 + 2/x + 1/x2 = 1/x2 + 1 K2 - 2K = (2K - 2)/x x = 2(K-1)/(K**2 - 2K)` [download] and so we can calculate K, and then calculate X, and then calculate everything else. But what about the general case? Well I half-way retract my analytic comment. There is an analytic approach - but it will be useless for practical purposes. As above, you can get rid of H and S by subtracting one from the rest, then dividing the rest by one remaining. That gives you 2 complex equations in various square roots of x and y. With a couple of squarings, both those equations can be turned into 4'th degree polynomials in x and y. There is an analytic solution to 4th degree polynomials (but it is very complex), so you can find y in terms of x and the other junk, and get high-order equation in terms of x alone. With some more manipulation that can be turned into a polynomial, and there is a general solution known to n'th degree polynomials using integrals. So in principle you can write down an exact solution. But the solution will be absurdly complex, and probably won't be as easy to calculate as a naive numerical approach.	[reply] [d/l] [select]