1983/11/01 by Nimrod Megiddo · 1 citation
Computer Science · Business, Management and Accounting · Mathematics · #Computational Geometry and Mesh Generation #Facility Location and Emergency Management #Mathematics #Combinatorics #Dimension (graph theory) #Center (category theory) #Plane (geometry) #Point (geometry) #Set (abstract data type) #Euclidean geometry #Upper and lower bounds #Euclidean distance #Discrete mathematics #Geometry #Mathematical analysis
paper · doi:10.1287/moor.8.4.498
openalex publication_date 1983/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
We present an O(n(log n) 3 (log log n) 2 ) algorithm for the problem of finding a point (x, y) in the plane that minimizes the maximal weighted distance to a point in a set of n given points. The algorithm can be extended to higher dimensional spaces. For any fixed dimension our bound is o(n 1+ϵ ) for any ϵ > 0.