Geometric median in nearly linear time

2016/06/10 by Michael B. Cohen, Yin Tat Lee, Gary L. Miller +2 · 109 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #3D Shape Modeling and Analysis #Euclidean geometry #Time complexity #Combinatorics #Point (geometry) #Computational geometry #Chin #Mathematics #Running time #Algorithm #Geometry

paper · pdf · doi:10.1145/2897518.2897647

openalex publication_date 2016/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

In this paper we provide faster algorithms for solving the geometric median problem: given n points in d compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O(d· n4/3є−8/3) by Chin et. al, Õ(dexpє−4logє−1) by Badoiu et. al, O(nd+poly(d,є−1)) by Feldman and Langberg, and the polynomial running time of O((nd)O(1)log1/є) by Parrilo and Sturmfels and Xue and Ye.

Citations

• A unified framework for approximating and clustering data
• Fast approximations for sums of distances, clustering and the Fermat–Weber problem
• Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem
• The multivariate L 1 -median and associated data depth
• A note on Fermat's problem
• The algebraic degree of geometric optimization problems
• On Torricelli's geometrical solution to a problem of Fermat

Cited by

• Geometric median [wikipedia]