On the Fermat-Weber center of a convex object

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

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)188-195
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume32
Issue number3
DOIs
StatePublished - Nov 1 2005

Keywords

  • Approximation algorithms
  • Fermat-Weber center

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'On the Fermat-Weber center of a convex object'. Together they form a unique fingerprint.

  • Cite this