Personal tools
You are here: Home CG seminar Spring 2017 The planar separator strikes back: exact, approximate and quasi polynomial algorithms
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
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