On the Fermat-Weber center of a convex object (Q2571212): Difference between revisions

A Fermat-Weber center of a point set \(S\) is a point that minimizes the average distance to the points in \(S\). The authors consider the case in which \(S\) is a convex object \(Q\) in the plane, and distances are measured by the Euclidean metric. For \(\Delta(Q)\) being the diameter of \(Q\), the authors show that the average distance of a Fermat-Weber center to the points in \(Q\) is always greater than \(\Delta/7\), and give an example for which \(\Delta/6\) is achieved. This result is used to obtain a linear-time approximation scheme for finding an approximate Fermat-Weber center of a convex polygon \(Q\).