Finding an Euclidean anti-kk-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 kk smallest weighted Euclidean distances to nn given points, each protected by some polygonal forbidden region. For the unweighted case and kk fixed an O(n2logn)O(n2logn) time algorithm is presented. For the weighted case a thorough study of the relevant structure of the multiplicatively weighted order-kk-Voronoi diagram leads to the design of an O(kn3+n3logn)O(kn3+n3logn) time algorithm for finding an optimal solution to the anti-tt-centrum problem for every t=1,…,kt=1,…,k, simultaneously.