Home Bookmarks Papers Blog

On the Fermat-Weber Center of a Convex Object

Paz Carmi, Sariel Har-Peled, and Matthew J. Katz.

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 \Diam(P)/7, where \Diam(P) is the diameter of P, and that there exists a convex object for which this distance is \Diam(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.

Postscript, PDF.

  author    = {Paz Carmi and
               Sariel Har-Peled and
               Matthew J. Katz},
  title     = {On the Fermat-Weber center of a convex object.},
  journal   = {Comput. Geom.},
  volume    = {32},
  number    = {3},
  year      = {2005},
  pages     = {188-195},
  ee        = {http://dx.doi.org/10.1016/j.comgeo.2005.01.002},
  bibsource = {DBLP, http://dblp.uni-trier.de}

Last modified: Thu Nov 17 00:04:19 CST 2005