SERVING THE QUANTITATIVE FINANCE COMMUNITY

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Extremes

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.

ppauper
Posts: 68466
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

How would Euler have solved that problem (e.g. calculus of variations)?

ppauper
Posts: 68466
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

Cuchulainn wrote:
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)

Paul
Posts: 8530
Joined: July 20th, 2001, 3:28 pm

### Re: Extremes

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

The Collector is your man for square roots!

Collector
Posts: 3838
Joined: August 21st, 2001, 12:37 pm

### Re: Extremes

Paul wrote:
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!

katastrofa
Posts: 6135
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

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

Paul
Posts: 8530
Joined: July 20th, 2001, 3:28 pm

### Re: Extremes

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.

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

Paul wrote:
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

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

ppauper wrote:
Cuchulainn wrote:
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.

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

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

ppauper
Posts: 68466
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

Cuchulainn wrote:
Paul wrote:
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.

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

katastrofa wrote:
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

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.

katastrofa
Posts: 6135
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

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

Cuchulainn
Topic Author
Posts: 56684
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

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_median#Computation

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...