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 @D(Q)/7, where @D(Q) is the diameter of Q, and that there exists a convex object P for which this distance is @D(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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.comgeo.2005.01.002 | Comput. Geom. |
Keywords | Field | DocType |
fermat–weber center,convex object p,approximation algorithms,convex object,fermat-weber center,approximate fermat-weber center,linear-time approximation scheme,convex polygon,average distance,linear time | Orthogonal convex hull,Discrete mathematics,Combinatorics,Convex combination,Convex hull,Krein–Milman theorem,Convex polygon,Convex set,Convex polytope,Mathematics,Convex analysis | Journal |
Volume | Issue | ISSN |
32 | 3 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
12 | 1.15 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paz Carmi | 1 | 321 | 43.14 |
Sariel Har-Peled | 2 | 2630 | 191.68 |
Matthew J. Katz | 3 | 225 | 19.92 |