On the Fermat-Weber center of a convex object

摘要

We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least Delta(Q)/7, where A(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Delta(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat-Weber center of a convex polygon Q. (c) 2005 Elsevier B.V. All rights reserved.