Finding an Euclidean anti-k-centrum location of a set of points

摘要

An obnoxious facility is to be located inside a polygonal region of the plane, maximizing the sum of the k smallest weighted Euclidean distances to n given points, each protected by some polygonal forbidden region. For the unweighted case and k fixed an O(n~2 logn) time algorithm is presented. For the weighted case a thorough study of the relevant structure of the multiplicatively weighted order-k-Voronoi diagram leads to the design of an O(kn~3 + n~3 log n) time algorithm for finding an optimal solution to the anti-rnt-centrum problem for every f = 1,.....k, simultaneously.