Dissertation : Organizing Point Sets: Space-Filling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes
Betreuer: Prof. Dr. Günter Rote
For the analysis of an algorithm often the worst case is considered, i.e. how bad can the algorithm perform considering all possible inputs. This case does not necessarily capture the typical performance of the algorithm. In the geometric context, a structure defined by a worst case point set does not necessarily have typical properties of this structure.
In this work the role of randomness in constructing geometric structures is considered, i.e. how points coming from some random distribution influence the corresponding geometric structures and how this relates to the design and analysis of algorithms for constructing these structures. As geometric structures the Delaunay tessellation and related structures are considered.
This work focuses on incremental construction algorithms, i.e. algorithms constructing a geometric structure by adding points one by one, updating the structure in every step. Randomized incremental construction, where points are inserted in a random order, together with a point location data structure storing information about the construction process often results in an expected worst case optimal algorithm. But both the full randomization and the point location data structure can be unpractical in particular for large inputs. In this work partially randomized insertion orders together with other point location methods are considered. For point location the space-filling curve heuristic is examined.