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

DOI10.1016/J.DISOPT.2011.02.004zbMATH Open1233.90217arXiv1002.0345OpenAlexW2036207413MaRDI QIDQ665992FDOQ665992

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

Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

discrete geometryapproximation algorithmsconvex body

Mathematics Subject Classification ID

Continuous location (90B85)

Cites Work

• Minimum-cost load-balancing partitions
• On the Fermat-Weber center of a convex object
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On minimum stars and maximum matchings.
• On the continuous Weber and k -median problems (extended abstract)
• New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body
• On stars and Steiner stars
• Improved bounds on the average distance to the Fermat-Weber center of a convex object

Cited In (5)

• On the upper bound on the average distance from the Fermat-Weber center of a convex body
• 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 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)