The planar separator strikes back: exact, approximate and quasi polynomial algorithms

The planar separator theorem has been a useful tool for solving many kinds of geometric problems for decades. There has been some resurgence in using this tool in the last few years, with the emergence of a new methodology for designing approximation algorithms that uses the theorem as a main ingredient. We review some new exact and approximation algorithms that use the planar separator theorem as the main component. These results include the k-center problem, where our task is to compute a set of k discs of minimal radius that covers a given set of points, the disk cover problem, where our task is to compute a subset of a set of discs of minimal size that covers a given set of points, and the segment tiling problem, where our task is to compute a subset of a set of segments that induces a triangulation of a set of points.