Subquadratic algorithms for the weighted maximin facility location problem.
Frank Follert, Elmar Schömer, Jürgen Sellen · Canadian Conference on Computational Geometry · 1995
Let S be a set of n points in the plane, and let each point p of S have a positive weight w(p). We consider the problem of positioning a point x inside a compact region R ⊆ R such that min{ w(p)−1 · d(x, p) ; p ∈ S } is maximized. Based on the parametric search paradigm, we give the first subquadratic algorithms for this problem, with running time O(n log n). Furthermore, we shall introduce the concept of ‘exact approximation’ as the bit model counterpart to parametric search. Exploiting ideas from exact computation, we show that the considered problem can be solved in time O(Lμ(L)n log n), where L denotes the maximal bit-size of input numbers, and μ(L) the complexity of multiplying two L-bit integers.