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

DOI10.1016/J.DISOPT.2011.02.004MaRDI QIDQ665992zbMATHOpenAlexFDO

Authors Adrian Dumitrescu, Csaba D. Tóth, Minghui Jiang

Publication date 7 March 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.0345

zbMATH Keywords

discrete geometryapproximation algorithmsconvex body

Mathematics Subject Classification ID

Continuous location (90B85)

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/6cdotDelta(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 $frac2(4-sqrt3)13cdotDelta(Q)<0.3490cdotDelta(Q)$. The new bound substantially improves the previous bound of $frac23sqrt3cdotDelta(Q)approx0.3849cdotDelta(Q)$ due to Abu-Affash and Katz, and brings us closer to the conjectured value of $1/3cdotDelta(Q)$. We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.

Recommendations

• New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body
• A new approach to the upper bound on the average distance from the Fermat-Weber center of a convex body
• On the upper bound on the average distance from the Fermat-Weber center of a convex body
• Improved bounds on the average distance to the Fermat-Weber center of a convex object
• On the Fermat-Weber center of a convex object
• Lattice point inequalities for centered convex bodies
• New bounds on the dimensions of planar distance sets
• A generalization of the Minkowski distance and new definitions of the central conics
• On convex sets that minimize the average distance
• On Banach-Mazur distance between planar convex bodies

Cites work

• scientific article; zbMATH DE number 1803754 (Why is no real title available?)
• scientific article; zbMATH DE number 3160756 (Why is no real title available?)
• scientific article; zbMATH DE number 1253040 (Why is no real title available?)
• Improved bounds on the average distance to the Fermat-Weber center of a convex object
• Minimum-cost load-balancing partitions
• New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body
• On minimum stars and maximum matchings.
• On stars and Steiner stars
• On the Fermat-Weber center of a convex object
• On the continuous Weber and k -median problems (extended abstract)

Cited in

(5)

• A new approach to the upper bound on the average distance from the Fermat-Weber center of a convex body
• New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body
• On the upper bound on the average distance from the Fermat-Weber center of a convex body
• On the Fermat-Weber center of a convex object
• Improved bounds on the average distance to the Fermat-Weber center of a convex object

This page was built for publication: New bounds on the average distance from the Fermat-Weber center of a planar convex body

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q665992)