Serving the Quantitative Finance Community

 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Extremes

June 13th, 2018, 12:37 pm

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.
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 13th, 2018, 4:24 pm

 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 13th, 2018, 4:50 pm

How would Euler have solved that problem (e.g. calculus of variations)?
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 14th, 2018, 5:11 am

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)
 
User avatar
Paul
Posts: 6604
Joined: July 20th, 2001, 3:28 pm

Re: Extremes

June 14th, 2018, 6:11 am

You could spend a week trying to find the fastest solution.

The Collector is your man for square roots!
 
User avatar
Collector
Posts: 2572
Joined: August 21st, 2001, 12:37 pm
Contact:

Re: Extremes

June 14th, 2018, 8:50 am

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!
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 14th, 2018, 11:57 pm

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)
Last edited by katastrofa on June 17th, 2018, 6:18 pm, edited 1 time in total.
 
User avatar
Paul
Posts: 6604
Joined: July 20th, 2001, 3:28 pm

Re: Extremes

June 15th, 2018, 7:06 am

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.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 16th, 2018, 11:15 am

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.
Last edited by Cuchulainn on June 16th, 2018, 11:47 am, edited 4 times in total.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 16th, 2018, 11:28 am

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.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 16th, 2018, 3:48 pm

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..
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 16th, 2018, 6:25 pm

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.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 17th, 2018, 2:54 pm

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.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 17th, 2018, 5:11 pm

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.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 17th, 2018, 6:21 pm

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