Assigning Weights to Minimize the Covering Radius in the Plane

Abstract

Given a set $P$ of $n$ points in the plane and a multiset $W$ of $k$ weights with $k\le n$, we assign each weight in $W$ to a distinct point in $P$ to minimize the maximum weighted distance from the weighted center of $P$ to any point in $P$. In this paper, we give two algorithms which take $O(k^2{n}^2{\log }^{3}n)$ time and $O(k^{5}n{\log }^{3}k+kn{\log }^{3}n)$ time, respectively. For a constant $k$, the second algorithm takes only $O(n{\log }^{3}n)$ time, which is near linear.