Personal tools
You are here: Home CG seminar Spring 2017 The planar separator strikes back: exact, approximate and quasi polynomial algorithms
« July 2017 »
July
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

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

Wednesday, May 24th, 2017 16:10

Schreiber 309

underline

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 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.
Document Actions