Page 1 of 3

Extremes

Posted: June 13th, 2018, 12:37 pm
by Cuchulainn
Consider a general planar triangle. Find the point (in the interior of the triangle) the sum of whose (Euclidean) distances from the triangle's vertexes is the smallest possible.

Re: Extremes

Posted: June 13th, 2018, 4:24 pm
by ppauper

Re: Extremes

Posted: June 13th, 2018, 4:50 pm
by Cuchulainn
How would Euler have solved that problem (e.g. calculus of variations)?

Re: Extremes

Posted: June 14th, 2018, 5:11 am
by ppauper
How would Euler have solved that problem (e.g. calculus of variations)?
that's not clear from wiki
I followed link #1 to The Fermat Point and Generalizations, which presents several solutions, none of which I've read in any detail but all of which seem to depend very heavily on geometry
I did fire up maple and look at calculus of variations, but the general case is too complicated, square roots all over the place.
It was able to solve for specific triangles, which probably doesn't help you
call L the sum of the lengths and solve dL/dx=0 and dL/dy=0 for x and y
e.g. vertices (0,0), (4,0), (3,1) gives (2.985216071,0.9340030374)

Re: Extremes

Posted: June 14th, 2018, 6:11 am
by Paul
You could spend a week trying to find the fastest solution.

The Collector is your man for square roots!

Re: Extremes

Posted: June 14th, 2018, 8:50 am
by Collector
You could spend a week trying to find the fastest solution.

The Collector is your man for square roots!
yes my first degree is garden plants, I digged up a lot of roots by hand! It is indeed an art!

Re: Extremes

Posted: June 14th, 2018, 11:57 pm
by katastrofa
The problem is trivial for a physicist*. Imagine that you attach one end of a spring (stiffness k) to each vertex and connect the free ends together. The system of springs will minimise its potential energy, i.e. k/2*(x1^2+x2^2+x3^2), by achieving the equilibrium. In equilibrium the forces kx1, kx2 and kx3 counter-balance each other, which means the angles between their vectors are 2*pi/3.

*) Tomorrow morning, when I will have hopefully remembered my name, I will check if this solution makes sense :-D (error in the first equation corrected; solution for the actual Fermat point in my next post)

Re: Extremes

Posted: June 15th, 2018, 7:06 am
by Paul
The 2 pi/3 is fairly obvious (physics/small perturbations). Does that make it much easier to actually find the point? Probably. It suggests that doing things with equilateral triangles (pi/3) might be helpful.

Re: Extremes

Posted: June 16th, 2018, 11:15 am
by Cuchulainn
The 2 pi/3 is fairly obvious (physics/small perturbations). Does that make it much easier to actually find the point? Probably. It suggests that doing things with equilateral triangles (pi/3) might be helpful.
Assuming there is a computable solution (does it exist and is it unique?) for the equilateral triangle T then transform the original triangle to T, compute the point and perform the inverse transform (like finding intersection of two ellipses by transforming them to circles and doing the radical axis trick).
There's several hidden assumption here, which is fine. They should be flagged and they might even break down.

Reducing the scope (initially) does no harm.

Re: Extremes

Posted: June 16th, 2018, 11:28 am
by Cuchulainn
How would Euler have solved that problem (e.g. calculus of variations)?
that's not clear from wiki
I followed link #1 to The Fermat Point and Generalizations, which presents several solutions, none of which I've read in any detail but all of which seem to depend very heavily on geometry
I did fire up maple and look at calculus of variations, but the general case is too complicated, square roots all over the place.
It was able to solve for specific triangles, which probably doesn't help you
call L the sum of the lengths and solve dL/dx=0 and dL/dy=0 for x and y
e.g. vertices (0,0), (4,0), (3,1) gives (2.985216071,0.9340030374)
In the past we developed C++ code for CAD applications and there was always the choice between a geometric and an algebraic solution. I think this is a similar discussion.
A closed solution is probably not possible(?) but we can use Pythagoras to write the formula in terns of the unknown point and the known vertices. It is a minimisation problem. Should we not give constraints to state that the desired point to be in the interior of the triangle?  A similar problem is to find the shortest distance exterior to the triangle?

BTW I see only three square roots in the objective function.

Re: Extremes

Posted: June 16th, 2018, 3:48 pm
by Cuchulainn
Does the point exist that minimises the distance? Since a triangle is convex and the objective function can be cast as a sum of convex functions of the form [$]f(x) = \sqrt x[$] then a local minimum is a global minimum.

Assuming that we can cast it as an optimisation problem in the first place..

Re: Extremes

Posted: June 16th, 2018, 6:25 pm
by ppauper
The 2 pi/3 is fairly obvious (physics/small perturbations). Does that make it much easier to actually find the point? Probably. It suggests that doing things with equilateral triangles (pi/3) might be helpful.
Assuming there is a computable solution (does it exist and is it unique?) for the equilateral triangle T then transform the original triangle to T, compute the point and perform the inverse transform (like finding intersection of two ellipses by transforming them to circles and doing the radical axis trick).
There's several hidden assumption here, which is fine. They should be flagged and they might even break down.

Reducing the scope (initially) does no harm.
for an equilateral triangle with vertices at (0,0), (1,0) and (1/2,1/2*sqrt(3)) then (X,Y)=(1/2,1/(2*sqrt(3))) is the point that minimizes the sum of the distances
if you look at (d/dx) and (d/dy) at that point, and the second derivatives, it's a minimum

For the general case, kata's point about 2Pi/3 sounds right, so you can use geometry
If the vertices are at (x1,y1), (x2,y2) and (x3,y3) and the point is (X,Y) then the slope of the line from vertex 1 to the point is [$]\tan\theta_{1}=\frac{Y-y_{1}}{X-x_{1}}[$] and so on and then enforcing the angles between them leads to some messy equations for X and Y involving square roots.
Again, I'm not seeing nice neat expressions, just something that looks like it has to be solved numerically.
And indeed, I don't recall seeing an actual solution written down on that wiki page, just a description in words of what it was.

That page I linked contains several geometric methods. Maybe look them over and find the one you like best.

Re: Extremes

Posted: June 17th, 2018, 2:54 pm
by Cuchulainn
The problem is trivial for a physicist*. Imagine that you attach one end of a spring (stiffness k) to each vertex and connect the free ends together. The system of springs will minimise its potential energy, i.e. k*(x1+x2+x3), by achieving the equilibrium. In equilibrium the forces kx1, kx2 and kx3 counter-balance each other, which means the angles between their vectors are 2*pi/3.

*) Tomorrow morning, when I will have hopefully remembered my name, I will check if this solution makes sense :-D
This approach looks more like computing the centroid, whereas the current problem is the geometric median, ?
The problem can be posed as in convex analysis, making life easier. In general, it has been proved that no explicit formula exists,.so either symbolic/numerical is needed.

Re: Extremes

Posted: June 17th, 2018, 5:11 pm
by katastrofa
If we want to minimise the sum of distances, the spring analogy is incorrect. The springs would minimise the sum of squares of the distances (as the potential energy of a spring is proportional to the square of the stretch x, i.e. k/2 x^2). For the minimum sum of distances (S = d1+d2+d3) one needs to draw a physical analogy to three strings tied at one end (the knot situated at the Fermat point), and each string is pulled at the other end with the same strength in the direction of one of the triangle vertexes. The system will minimise the potential energy when the forces F1, F2 and F3 cancel out. The work done by those forces is proportional to the shift of the knot in the force direction, W1 = F1 * delta d1 = F * delta d1 and so on. Thus, minimising the total energy minimises the sum of distances S. It's a constrained optimisation problem, like in the drawing in the attached photo.

Re: Extremes

Posted: June 17th, 2018, 6:21 pm
by Cuchulainn
For an equilateral triangle with vertices at (0,0), (1,0) and (1/2,1/2*sqrt(3)) then (X,Y)=(1/2,1/(2*sqrt(3))) is the point that minimizes the sum of the distances

if you look at (d/dx) and (d/dy) at that point, and the second derivatives, it's a minimum


For this case I get (1/2, 0.288674) using derivative-free Differential Evolution and the constraint is the triangle's bounding box. 
For n points (polygon), we can use Weisfeld's algorithm.

https://en.wikipedia.org/wiki/Geometric ... omputation