Generalized Fermat Point
------------------------
Given a set of points, find a central point so that the sum of the
distances from the central point to all the other points is minimal.
That is, find the point p that minimizes
---
S(p) = > |p - p | [1]
--- k
k
To minimize S(p), we compute its gradient
--- p - p_k
grad(S(p)) = > --------- [2]
--- |p - p_k|
k
Later we will also need the partial sum over all {p_k} but one
---
S (p) = > |p - p | [1a]
k --- j
j<>k
and its gradient
--- p - p_j
grad(S (p)) = > --------- [2a]
k --- |p - p_j|
j<>k
Define the auxiliary functions
--- 1
R(p) = > --------- [3]
--- |p - p_k|
k
1 --- p_k
M(p) = ---- > --------- [4]
R(p) --- |p - p_k|
k
Combining [2], [3], and [4], we get that
grad(S(p)) = R(p) (p - M(p)) [5]
Since R(p) > 0, at an extremum of S(p), M(p) = p.
Lemma 1
-------
For a and b > 0,
a^2 - b^2
a - b >= --------- [6]
2 a
Proof
-----
Notice that
a^2 - b^2
a - b = --------- [6a]
a + b
If a = b, then [6a] yields equality in [6].
If a > b, then both sides of [6a] are greater than 0. Multiplying [6a]
by the inequality 1 > (a+b)/(2a), yields inequality in [6].
If a < b, then both sides of [6a] are less than 0. Multiplying [6a] by
the inequality 1 < (a+b)/(2a), yields inequality in [6].
QED
Theorem 1
---------
1 2
S(p) - S(M(p)) >= - R(p) |p - M(p)| [7]
2
Proof
-----
Using Lemma 1,
S(p) - S(M(p))
---
= > |p - p | - |M(p) - p |
--- k k
k
--- |p - p_k|^2 - |M(p) - p_k|^2
>= > ----------------------------
--- 2 |p - p_k|
k
--- |p|^2 - |M(p)|^2 + 2 p_k . (M(p) - p)
= > -------------------------------------
--- 2 |p - p_k|
k
--- |p|^2 - |M(p)|^2 + 2 M(p) . (M(p) - p)
= > --------------------------------------
--- 2 |p - p_k|
k
1 2
= - R(p) |p - M(p)|
2
QED
Corollary 1
-----------
S(M(p)) <= S(p) with equality only when M(p) = p.
Proof
-----
Follows immediately from Theorem 1.
Lemma 2
-------
For non-zero vectors u and v,
u v 1 1
( --- - --- ) . (u - v) = ( --- + --- ) (|u||v| - u.v) [8]
|u| |v| |u| |v|
Proof
-----
Expand both sides.
QED
Corollary 2
-----------
For p and q points not in {p_k},
( grad(S(p)) - grad(S(q)) ) . (p - q) >= 0 [9]
If p <> q and the {p_k} do not all lie in a line, [9] is strict.
Furthermore, even if the {p_k} all lie in a line, if p <> q and either
p or q does not lie on that line, [9] is strict.
Proof
-----
Using [2] and Lemma 2,
( grad(S(p)) - grad(S(q)) ) . (p - q)
--- p - p_k q - p_k
= > ( --------- - --------- ) . (p - q)
--- |p - p_k| |q - p_k|
k
--- 1 1
= > ( --------- + --------- ) ( |p - p_k||q - p_k| - (p - p_k).(q - p_k) )
--- |p - p_k| |q - p_k|
k
>= 0 [10]
where equality holds in [10] if and only if p - p_k and q - p_k are in
exactly the same direction for all k. Thus, equality can hold only if
p = q or all the {p_k} lie in a line and p and q are on that line.
Thus, if p <> q and the {p_k} do not all lie in a line, [10] is strict.
Furthermore, even if the {p_k} all lie in a line, if p <> q and either
p or q does not lie on that line, [10] is strict.
QED
Lemma 3
-------
If u . v > 0, then
a. |u + v| > |u|
b. |u + v| > |v|
Proof
-----
Note that
2 2 2
|u + v| = |u| + |v| + 2 u . v
Since u . v > 0, we have both of the inequalities above.
QED
Corollary 3
-----------
If the {p_k} do not all lie in a line, then
a. grad(S(p)) is 1-1
b. |grad(S(p)) - grad(S_k(p_k))| > 1
c. |grad(S_k(p_k)) - grad(S_m(p_m))| > 2
where S_k is defined as in [1a].
Proof
-----
a. Corollary 2 says that ( grad(S(p)) - grad(S(q)) ) . (p - q) > 0 when
p <> q and the {p_k} do not all lie in a line. Thus, grad(S(p)) is 1-1.
b. From the definitions
grad(S(p)) - grad(S (p ))
k k
--- p-p_j p_k-p_j p-p_k
= > ( ------- - --------- ) + ------- [11]
--- |p-p_j| |p_k-p_j| |p-p_k|
j<>k
Removing p_k from the {p_j}, Corollary 2 says that
--- p-p_j p_k-p_j
> ( ------- - --------- ) . (p - p ) > 0 [12]
--- |p-p_j| |p_k-p_j| k
j<>k
Thus, letting u be the sum over j<>k and v be (p-p_k)/|p-p_k|, we get,
using Lemma 3 with [11] and [12],
|p-p_k|
|grad(S(p)) - grad(S (p ))| > ------- = 1
k k |p-p_k|
c. From the definitions
grad(S (p )) - grad(S (p ))
k k m m
--- p_k-p_j p_m-p_j p_k-p_m p_m-p_k
= > ( --------- - --------- ) + --------- - ---------
--- |p_k-p_j| |p_m-p_j| |p_k-p_m| |p_m-p_k|
j<>k,m
--- p_k-p_j p_m-p_j p_k-p_m
= > ( --------- - --------- ) + 2 --------- [13]
--- |p_k-p_j| |p_m-p_j| |p_k-p_m|
j<>k,m
Removing p_k and p_m from the {p_j}, Corollary 2 says that
--- p_k-p_j p_m-p_j
> ( --------- - --------- ) . (p - p ) > 0 [14]
--- |p_k-p_j| |p_m-p_j| k m
j<>k,m
Using Lemma 3 with [13] and [14] as above, we get
|p_k-p_m|
|grad(S (p )) - grad(S (p ))| > 2 --------- = 2
k k m m |p_k-p_m|
QED
Let us look at the behavior of grad(S(p)) near p_k.
grad(S(p + e))
k
e
= grad(S (p + e)) + ---
k k |e|
e
-> grad(S (p )) + ---
k k |e|
as |e| -> 0. That is, as p circles close to p_k, grad(S(p)) circles
grad(S_k(p_k)) at distance 1.
Theorem 2
---------
If the {p_k} do not lie in a line, there is a unique minimum of S(p).
Proof
-----
Using [2], it is easily seen that outside the convex hull of the {p_k},
grad(S(p)) cannot be 0 since all the summands in [2] lie along the arc
of the unit circle opposite that containing the convex hull. Thus,
moving toward the bisector of the arc containing the convex hull will
decrease S(p). Therefore, the infimum of S(p) is the infimum of S(p)
on the convex hull of the {p_k}.
S(p) is continuous on the convex hull of the {p_k}, which is compact.
Therefore, S(p) attains its infimum on the convex hull of the {p_k}.
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.
QED
Finding the Fermat Point
------------------------
If |grad(S_k(p_k))| <= 1 for some k, then p_k is the fermat point.
If |grad(S_k(p_k))| > 1 for all k, then define the sequence of points
{q_k} starting with any q_0 and then
q = M(q )
k+1 k
Looking at [4], M(p) is a weighted mean of the {p_k}. Therefore, M(p)
is always in the convex hull of the {p_k}. This means that for k > 0,
q_k is in the convex hull of the {p_k}. Since the convex hull of the
{p_k} is compact, some subsequence of {q_k} converges.
Corollary 1 says that
S(q ) <= S(q )
k+1 k
Thus, S(q_k) has a limit as k->oo and that limit is the infimum of
{S(q_k)}.
Let {q1_k} be a convergent subsequence of {q_k} and q1 its limit. Since
M(p) is continuous, the subsequence of {q_k}, {M(q1_k)}, converges to
M(q1). Since S is continuous, S(q1) = S(M(q1)). Thus, by Corollary 1
M(q1) = q1, and therefore, by [5], grad(S(q1)) = 0. Thus, there is only
one limit point of {q_k} and it is the fermat point.
There are only a countable number of starting points, q_0, where M(q_k)
is in the {p_k}. If that should occur, pick another q_0.
Rob Johnson