The Weighted Euclidean 1-Center Problem

Abstract

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.