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 <= 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 present an algorithm which takes O(k(2)n(2) log(3)n) time for the problem. We also consider the case that all weights in W are at most 1, and present an O(k(5)n log(3)k + kn log(3)n)-time algorithm. For a constant k, it takes only O(n log(3)n) time, which is near linear. (C) 2019 Elsevier B.V. All rights reserved.