The State of the Union: Quickly Finding Gaps in Unions of High-Dimensional Rectangles

Organisatsiooni nimi
Algorithms & Theory
Kokkuvõte
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.
Lõputöö kaitsmise aasta
2016-2017
Juhendaja
Dirk Oliver Theis
Suhtlemiskeel(ed)
inglise keel
Nõuded kandideerijale
Analysis of algorithms
Tase
Magister
Märksõnad
#tcs

Kandideerimise kontakt

 
Nimi
Dirk Oliver Theis
Tel
E-mail
dotheis@ut.ee