Article ID Journal Published Year Pages File Type
10327622 Computational Geometry 2005 8 Pages PDF
Abstract
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 Δ(Q)/7, where Δ(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Δ(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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,