Fermat's Problem in Three Dimensions

  Verified the Newton's method works in three dimensions. I choose the  four vertices of a tetrahedron as the given points. The Fermat point which makes the sum of the distances from the given point a minimum turned out to be mean of the given points.

I used Excel to create an anaglyph. You will need red-cyan glasses to view it properly.

Is the Minimum for the Four Point Fermat Problem Where We Thought?

  I've been trying to convince myself that minimum in the four point Fermat problem of the last blog is not slightly displaced from the point c. The plot below shows changes in the sum L=Σℓ_i of the lengths of the links from the known points to the unknown point x for changes along two lines, u and v through the point (0.700,0.700) in the plane of x.

Below 0.700 both lines decrease and increase above this value. The slopes are fairly linear on each side. But it's difficult to be certain that point c is the actual minimum just going by the data because of the discontinuity in the slope. Notice that the angle from horizontal is not the same for both lines. It may be possible for the slope on the right to be decrease also but at a lower rate. But under the circumstances it does look like c is the actual point of intersection for the two line segments.

Supplemental (May 21): Obviously we can't use an extension of Newton's method to solve this type of minimum problem since the gradients are not zero at the minimum. Fermat's theory of maxima and minima is not a general theory. When doing searches for curve fits one often encounters local minima that appear to be line segments. This might happen if the minimum is paraboloidal in shape and the contour lines are elliptical.

An Insoluble Fermat Problem for the Method

 There's a four point Fermat problem that can't be solved by linearizing the function for the sum of the distances of the unknown point.

If one tries one ends up with division by zero. The gradient of L at point c is not continuous.

The distance function near a point is cone shaped.

The individual gradients are not well behaved near a given point as this plot shows.

For a problem like this one can compute the gradient function for two points displaced from the minimum and try to find where two lines in their directions through the chosen points intersect to get a better estimate of the minimum.

An Oversight on the Fermat Point Solution

  I just noticed an error in my the solution for the Fermat Point in the last blog but it didn't affect the results. One can solve the f correction equations for dx directly and the normal equations are not needed.

One can read f|_x≠0 as "f evaluated at x is not equal to zero." The normal equations are useful when one has more equations than unknowns which often occurs when one is doing least squares fits. This method might be considered the equivalent of Newton's method for finding the zero of an equation in higher dimensions.

Finding the Fermat Point Given Three Arbitrary Points

  At the end of a letter to Mersenne in about 1640 concerned with finding maxima and minima Fermat proposed this problem:

  "Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas."

  "Given three points, the forth to be found, from which you draw three lines to the given points, the sum of these three lines is to be a minimum quantity."

So, given three arbitrary points, and using the method in the previous blogs, we can find the Fermat point as follows. The distances are the ℓ_i whose sum is to be minimized. Taking the derivative we find for an assumed value of x that dL=f^Tdx where f is the sum of three unit vectors pointing to x. For the position of x for the minimum value of L the change dL has to be zero for arbitrary changes in position, dx, and the only way that this can happen is if f is equal to zero too. But the value of f at the assumed point is not necessarily zero so we look at changes in f with position and see find the value of dx for which f+df=f+Mdx=0. These are the correction equations for f. The matrix M is found by extracting the derivative of the vector function f(x). Using the method of least squares one can show that dx is a solution of the normal equations.

Using the above equations in Excel and repeatedly correcting the value for x we arrive at the Fermat point after just a few iterations.

Checking the angles between the lines from x to the given points we find they are all 120° which was deduced from the minimum condition.

The correction equations for Fermat's problem are simpler than the reflection problem since we do not have a constraint on the change for dx.

Reflection as an Example of the Shortest Path for Light

  There's a simpler version of the Steiner Tree Problem and that is Hero's problem of finding the shortest path for a reflected ray of light. Again, for the general problem, we have the "gradient" equal to the sum of two unit vectors pointing to the unknown point, x. An additional complication is the constraint of the motion of x along a line so that dx=îdx'.

A solution for the reduced normal equations verifies that the angle of incidence equals the angle of reflection.

Reflecting the second point above the line illustrates Euclid's Prop. XX in his Elements Bk 1 asserting the sum of any two sides of a triangle is greater than the third or, equivalently, a straight line is the shortest distance between two points.

One can see that the triangles in the two problems are similar and the math works out the same.

Solving a Steiner Tree Problem in Excel

  Solving a Steiner tree problem can be challenging but I managed to get Excel to do this using an iterative process for correcting the positions of the unknown points. The problem seeks to find a set of links between a number of points that has a minimal sum for the lengths. One can derive the minimum conditions as follows. The required condition is that the sum of a set of unit vectors toward or away from the unknown points x and y is equal to zero.

Note that the conditions imply that these unit vectors can be arranged to form the sides of an equilateral triangle making the angles at the points x and y equal to 120°.

The conditions for minimum are not linear making them difficult to solve for x and y but we can linearize them by assuming values for x and y and seeking corrections dx and dy for which the above functions are zero.

The values for x and y allow one to find the corrections dx and dy which produce the more accurate solutions x' and y'. One nice thing about Excel is that one can use a macro to replace the original values of x and y with the new ones, x' and y', and rapidly recompute them using a shortcut key such as Ctrl-Shift-R.

Binomial Distribution Fit Curvature

  If one takes the natural log of the probabilities for the binomial distribution and the fit in the last blog one gets the curves below. The 2nd differences which are a measure of the curvature of the curves are also given. The 2nd differences for the fit are constant as expected.

The relatively large differences at the ends are less critical since they correspond to relatively small values for the probabilities.

Supplemental (May 9): The 2nd differences for the normal distribution function are also uniform and equal to -0.04 or 1/λ exactly.

Supplemental (May 10): Technically, curvature depends on changes in the tangent of a curve with path length but I think it's fair to say that deviation from a straight line is a form of curvature even if it is not constant. For a parabolic arc the rate of change of the slope with a change in the "horizontal" distance is constant. I got Excel to find a center for the circular arc of the lower curve of the second plot above and radius of curvature turned out to be a little over 25,000. We don't have to worry about units here since both axes are just real numbers.

The Normal Dist. as an Empirical Fit to the Binomial Dist.

  The binomial distribution is a rather complicated function and the factorials are difficult to deal with so one might be tempted to seek a simpler function that approximates it. The binomial distribution is fairly symmetric about the mean value, μ, and a logarithmic plot reveals an approximate quadratic function so we might try to fit a function of the form,

This is a discrete probability function and its sum over all values of k is equal to 1 so A is actually a function of β too. We could try a search for β that minimizes the mean square error or find an approximate solution and try to improve on it. The second method gave the following fit.

The first plot compares the fit with the binomial distribution which is quite good in this example. The red points in the second plot show the deviation of the fit from the binomial distribution and the blue points give the same for the normal distribution formula using the  expected values <k> for μ and <k²> for λ. For most values of p the two error "curves" are nearly equal but for p near 1/2 the least squares fit has lower bounds on the error.

Supplemental (May 8): Recomputed the normal distribution error evaluating the erf function at k±0.5 to get:

The curvature of the binomial distribution near the peak and wings may be responsible for the deviations of the two approximation functions.