|
|||||
|
|
On the Fermat–Weber center of a convex object |
|
| Authors: | Paz Carmi Sariel Har-Peled Matthew J Katz |
| Institution: | aDepartment of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel bDepartment of Computer Science, University of Illinois, 201 N. Goodwin Avenue, Urbana, IL 61801, USA |
| 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: | Fermat–Weber center Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |