New bounds on the average distance from the Fermat-Weber center of a planar convex body

Abstract

The Fermat-Weber center of a planar body $Q$ is a point in the plane from which the average distance to the points in $Q$ is minimal. We first show that for any convex body $Q$ in the plane, the average distance from the Fermat-Weber center of $Q$ to the points of $Q$ is larger than $1/6\cdot \Delta (Q)$, where $\Delta (Q)$ is the diameter of $Q$. This proves a conjecture of Carmi, Har-Peled and Katz. From the other direction, we prove that the same average distance is at most $\frac{2(4-\sqrt{3})}{13}\cdot \Delta (Q)<0.3490\cdot \Delta (Q)$. The new bound substantially improves the previous bound of $\frac{2}{3\sqrt{3}}\cdot \Delta (Q)\approx 0.3849\cdot \Delta (Q)$ due to Abu-Affash and Katz, and brings us closer to the conjectured value of $1/3\cdot \Delta (Q)$. We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.

13 pages, 2 figures. An earlier version (now obsolete): A. Dumitrescu and Cs. D. Tóth: New bounds on the average distance from the Fermat-Weber center of a planar convex body, in Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), 2009, LNCS 5878, Springer, pp. 132-141