
August
Su  Mo  Tu  We  Th  Fr  Sa 
    1  2  3 
4  5  6  7  8  9  10 
11  12  13  14  15  16  17 
18  19  20  21  22  23  24 
25  26  27  28  29  30  31 

 Info
The planar separator strikes back: exact, approximate and quasi polynomial algorithms
Wednesday, May 24th, 2017 16:10
Schreiber 309
The planar separator strikes back: exact, approximate and quasi polynomial algorithms
Nitzan Weissman, TAU
Abstract:
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 kcenter 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.
