Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10327622 | Computational Geometry | 2005 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Paz Carmi, Sariel Har-Peled, Matthew J. Katz,