Dissertation : Lifting Planar Graphs to Realize Integral 3-Polytopes and Topics in Pseudo-Triangulations
Betreuer: Prof. Dr. Günter Rote
Triangulations are a well known tool in Computational Geometry for designing and analyzing algorithms. They have many applications and are investigated widely.
Most recently pseudo-triangulations were defined as a more general concept. As for triangulations there exist many applications for them. Pseudo-triangulations were used in algorithms for ray shooting, collision detection, motion planning and many more. Beside of their application they combinatorial structure is from interest too. It turns out that pseudo-triangulations behave sometimes "nicer" than triangulations, i.e. they have a shorter flipping distance. On the other hand there exist also many similarities between triangulations and pseudo-triangulations (both can be represented as vertices of polytopes, both are connected by flips).
I'm interested in pseudo-triangulations with special properties as we know them for triangulation. As a first step I introduced the Delaunay pseudo-triangulations for simple polygons. The goal is to generalize this approach to arbitrary point sets. Are there other "special" pseudo-triangulations.
Furthermore I investigated questions about hardness problems in the pseudo-triangulation world. I showed that (like for triangulations) it is NP-hard to decide if we can finish a geometric graph to a pseudo-triangulation without violating a given vertex degree bound. As another result I want to show that it is hard to decide how to turn a planar graph to a minimum pseudo triangulation by removing edges. This topic needs further investigations.
As a third point i take care of polytopal representation of pseudo-triangulations. Until now several polytopes, which represent (a subclass) of pseudo-triangulations as their vertices, are known. I'm interested in the connection between them and in new descriptions of these or new polytopes. Furthermore I plan to use them for linear optimization. I have already shown, that there exist a general objective function for a class of simple polygons which gives us the Delaunay pseudo-triangulations.
There are many other aspects which might be covered in my thesis. For example I'm interested in the flipping distance between pseudo-triangulations. It is known that it is in O(n log n), but it is not clear if this bound is tight. Furthermore it would be interesting how fast a random flipping sequence is mixing the pseudo-triangulation.