From: Boudewijn Moonen <Boudewijn.Moonen@ipb.uni-bonn.de>
Subject: The Weiszfeld algorithm
Date: Wed, 28 Apr 1999 17:52:15 +0200
Newsgroups: sci.math,sci.math.research
Keywords:  Fermat-Weber problem, Steiner problem, facility location problem

On Mar 15 Timothy Keller wrote

>  Suppose one has n given points in R^2 , (x_i, y_i ), and one
>wishes to find a point ( X, Y ) so that the sum of the Euclidean
>distances s_i  from the ( x_i, y_i ) is a minimum.  Then the following
>fixed point sequence :
>
>                    X_k+1 = sum{x_i/s_i,k}/sum{1/s_i,k}
>
>                    Y_k+1 = sum{y_i/s_i,k}/sum{1/s_i,k}
>
>,where s_i,k is the distance from {x_i,y_i} to X_k,Y_k,
>is known to converge for ( I think ) any initial point ( X_0, Y_0 ).
>I rediscovered this algorithm when I was taking calculus II( more
>years ago than I care to remember).
>
>   Does anyone have a reference for the proof of the convergence
>of this sequence?  I know it exists, and have seen it listed, but
>can't remember any details.
>
>                             Thanks, Tim


The problem is known as the Fermat-Weber problem, the Steiner
problem, or the facility location problem. The algorithm
in question is known as the Weiszfeld algorithm. The original source
is

    E. Weiszfeld,  Sur le point pour lequel la somme des distances de
    n points donnés est minimum, Tôhoku Mathematics Journal 43
    (1937), 355 - 386.

When going through Weiszfeld's proof it appeared to me that
one needs additional conditions on the given points, e.g. that
no one is in the convex hull of the others, which are not
mentioned by Weiszfeld, but maybe I am wrong. I have
written a survey on Weiszfeld's proof where I comment
on this problem:

    ftp://ftp.uni-bonn.de/pub/staff/moonen/fw.ps.gz

Additional comments regarding the solution of this
question are appreciated. Furthermore I would
appreciate hints to further proofs of Weiszfeld's
theorem in the literature.

Regards



--
    Boudewijn Moonen
    Institut fuer Photogrammetrie der Universitaet Bonn
    Nussallee 15

    D-53115 Bonn

    GERMANY

    e-mail: Boudewijn.Moonen@ipb.uni-bonn.de
    Tel.:   GERMANY +49-228-732910
    Fax.:   GERMANY +49-228-732712
==============================================================================

From: Boudewijn Moonen <Boudewijn.Moonen@ipb.uni-bonn.de>
Subject: Re: The Weiszfeld algorithm - correction to ftp address
Date: Thu, 29 Apr 1999 14:53:40 +0200
Newsgroups: sci.math,sci.math.research

Boudewijn Moonen wrote:

>  I have written a survey on Weiszfeld's proof where I comment
> on this problem:
>
>     ftp://ftp.uni-bonn.de/pub/staff/moonen/fw.ps.gz
>

The correct address is

    ftp://ftp.ipb.uni-bonn.de/pub/staff/moonen/fw.ps.gz

--
    Boudewijn Moonen
    Institut fuer Photogrammetrie der Universitaet Bonn
    Nussallee 15

    D-53115 Bonn

    GERMANY

    e-mail: Boudewijn.Moonen@ipb.uni-bonn.de
    Tel.:   GERMANY +49-228-732910
    Fax.:   GERMANY +49-228-732712