The Weighted Euclidean 1-Center Problem

1 November 1983

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 8 (4) , 498-504
https://doi.org/10.1287/moor.8.4.498

Abstract

We present an O(n(log n)³(log log n)²) 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.

Keywords

WEIGHTED EUCLIDEAN
CENTER PROBLEM
PLANE
MAXIMAL
MINIMIZES
DISTANCE
SUP