Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams

Understand

We study a general family of facility location problems defined on planar graphs and on the 2-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^{O(k)}$ time brute force algorithm of selecting $k$ objects can be improved to $n^{O(\sqrt{k})}$ time.
• The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs.