The State of the Union: Quickly Finding Gaps in Unions of High-Dimensional Rectangles
Organization
Algorithms & Theory
Abstract
This is a proof-oriented computational geometry topic. Given as input a set of axis-parallel d-dimensional small boxes contained in a large box, decide if they cover the large box, or leave points uncovered.
The goal of the thesis is to:
1. review the available literature on the problem;
2. determine its complexity (NP-hardness)
3. produce approximation algorithms and prove performance guarantees
4. code the algorithms.
The goal of the thesis is to:
1. review the available literature on the problem;
2. determine its complexity (NP-hardness)
3. produce approximation algorithms and prove performance guarantees
4. code the algorithms.
Graduation Theses defence year
2016-2017
Supervisor
Dirk Oliver Theis
Spoken language (s)
English
Requirements for candidates
Analysis of algorithms
Level
Masters
Keywords
Application of contact
Name
Dirk Oliver Theis
Phone
E-mail