Having trouble with a minimum problem
Robert Kaufman
Given three distinct points, P1,P2,P3, not colinear,
consider the set of values d(P1,P) +d(P2,P)+d(P3,P)
for all points P where d(A,B) is the distance between
points A, and B and let m be the minimum of this set.
Is there an algorithm which we can use to find all points
Px for which we have d(P1,Px) + d(P2,Px) + d(P3,Px) = m?
Respectfully,
Robert Kaufman
Tim Little
> [...] let m be the minimum of this set. Is there an algorithm which
> we can use to find all points Px for which we have
> d(P1,Px) + d(P2,Px) + d(P3,Px) = m?
Sure, look up "Fermat point".
- Tim
Robert Kaufman
Tim, thank you very much for the reference.
Respectfully,
Robert Kaufman
Rob Johnson
About 30 years ago, I wrote up the article that I posted at
<http://www.whim.org/nebula/math/fermatpt.html>
It describes the problem you describe generalized to n points.
The Fermat point is unique, even in the n-point generalization,
unless there are an even number of points and they are collinear.
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
Ray Vickson
> In article <1095831636.61892.1293407351216.JavaMail.r...@gallium.mathforum.org>,
>
> Robert Kaufman <Yearachm...@verizon.net> wrote:
> >Given three distinct points, P1,P2,P3, not colinear,
> > consider the set of values d(P1,P) +d(P2,P)+d(P3,P)
> >for all points P where d(A,B) is the distance between
> >points A, and B and let m be the minimum of this set.
> >Is there an algorithm which we can use to find all points
> >Px for which we have d(P1,Px) + d(P2,Px) + d(P3,Px) = m?
>
> About 30 years ago, I wrote up the article that I posted at
>
> <http://www.whim.org/nebula/math/fermatpt.html>
>
> It describes the problem you describe generalized to n points.
That is a very interesting article. However, it seems to be based on
setting the gradient to zero, which is not always true at the minimum:
some problems will have the minimum sitting right on top of one of the
points, so there would be no well-defined gradient at such an optimum.
Of course, the zero vector is still a member of the subgradient set,
and all directional derivatives are >= 0 there, but I don't know if
the results of the paper generalize to such cases. As an example, take
three points at the vertices of an equilateral triangle. The Fermat
point is at the centroid. Now add a fourth point right at that
centroid. This problem will have a Fermat point right on one of the
given points.
R.G. Vickson
Pubkeybreaker
>
> - Show quoted text -
A big chunk of my undergrad dissertation addressed this problem and
some
variations. (e.g. weighted distances)
Let P be the minumim point. The sum of the *UNIT* vectors from this
point to each of the others must be zero. If the points form a
triangle you get what is known as a Steiner point. It occurs where
either the 3 internal angles formed by the vectors from the min to
each of the triangle points are all 120 degress, or at the vertex of
the triangle if the angle at that vertex exceeds 120.
Rob Johnson
Ray Vickson <RGVi...@shaw.ca> wrote:
>On Dec 29, 3:21=A0am, Rob Johnson <r...@trash.whim.org> wrote:
>> In article <1095831636.61892.1293407351216.JavaMail.r...@gallium.mathforu=>> >Given three distinct =A0points, P1,P2,P3, not colinear, =A0
>> > consider =A0the set of values d(P1,P) +d(P2,P)+d(P3,P)
>> >for all points P where d(A,B) is the distance between
>> >points A, and B and let m be the minimum of this set.
>> >Px for which we =A0have d(P1,Px) + d(P2,Px) + d(P3,Px) =3D m?
>>
>> About 30 years ago, I wrote up the article that I posted at
>>
>>
>> It describes the problem you describe generalized to n points.
>
>That is a very interesting article. However, it seems to be based on
>setting the gradient to zero, which is not always true at the minimum:
>some problems will have the minimum sitting right on top of one of the
>points, so there would be no well-defined gradient at such an optimum.
>Of course, the zero vector is still a member of the subgradient set,
>the results of the paper generalize to such cases. As an example, take
>three points at the vertices of an equilateral triangle. The Fermat
>point is at the centroid. Now add a fourth point right at that
>centroid. This problem will have a Fermat point right on one of the
>given points.
Perhaps I should have devoted more to the point, but in the proof of
Theorem 2, it is stated that
>There are two types of minima, a point where grad(S(p)) vanishes, and
>a p_k near which grad(S(p)) circles the origin. Corollary 3 shows
>that only one occurrence of one of these types can occur.
I believe that this covers the case you are talking about.