Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n …