On the Fermat-Weber center of a convex object (Q2571212)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Fermat-Weber center of a convex object |
scientific article |
Statements
On the Fermat-Weber center of a convex object (English)
0 references
1 November 2005
0 references
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\).
0 references
Fermat-Weber center
0 references
approximation algorithms
0 references