Spacial Decompositions and Graphs
Final Report Abstract
The straight skeleton of a polygon is a geometric structure that has important applications. In the plane, it has a straightforward definition, but in space, for general (non-convex) polytopes in space, there was no consistent definition so far. It was known that ambiguities can arise, and it was not even clear that a structure with analogous properties as in the plane always exists. The straight skeleton in 3D has now been canonically defined; it can be computed as the (minimal volume) offset of polytopes in 3D. There is for the fist time an implementation of an algorithm that computes such skeletons and handles also all ambiguities and degenerate cases (IP1). Reeb graphs form another important skeletal structure for shapes. We designed an algorithm for the Reeb graph of a 3D volume, which requires only the boundary representation. This algorithm has been implemented and tested, and it proved to be efficient for real-world examples. (IP2). Abstract Voronoi diagrams have been generalized to disconnected Voronoi regions and to k-th order Voronoi diagrams. For the latter we gave a complexity bound of 2k(n-k) which is asymptotically tight. Such a bound was previously known only for points under Lp norms and for line segments under the L2 Norm. (Joint work between IP5 and IP7). We found a simple proof for the fact that additively weighted Voronoi diagrams optimally solve the semi-discrete transportation problem for a large class of cost measures. This is interesting in connection with the transportation metric (or earthmovers-distance or Wasserstein metric) between probability distributions, which is important for shape matching but has recently gained interest in other fields such as variational principles for dynamical systems (Joint work between IP4 and IP5.) We have initiated a thorough study of planar graph drawings that use circular arcs, as a means to improve the readability of graph drawings when the location of the vertices is fixed. For the case of triangulations, we gave algorithms for optimizing the smallest occurring angle without introducing crossings. (Joint work between IP1, IP2 and IP5.) A major breakthrough has been achieved in close connection with the EuroGIGA Project, but not as part of EuroGIGA: Natan Rubin, who was associated to the group of IP4 at FU Berlin, has solved the longstanding open question of the number of changes of the Voronoi diagram of points moving on a line at unit speeds. We also gave a randomized divide and conquer method (based on the Clarkson-Shor framework), which constructs the order-k abstract Voronoi diagram in O(kn1+ε) expected time, where ε>0 is a constant. (Joint work between IP4 and IP7.) Linear time algorithms to compute tree-structured Voronoi diagrams of segments, such as the farthest segment Voronoi diagram and the order-(k+1) subdivision within and order-k. Voronoi region, after the sequence of their faces at infinity or an enclosing boundary is known. Extendible to the abstract counterparts. (IP7)
Publications
-
Convex hull alignment through translation, Proceedings of the 25th Canadian Conference on Computational Geometry, (CCCG'2013), 2013, pp. 295-300
Michael Hoffmann, Vincent Kusters, Günter Rote, Maria Saumell, and Rodrigo I. Silveira
-
On the Complexity of Higher Order Abstract Voronoi Diagrams. In: Proc. of the 40th ICALP (Riga, Latvia), pp. 208-219 (Part 1), 2013
Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou and Maksym Zavershynskyi
-
Optimally solving a transportation problem using Voronoi diagrams, Computational Geometry: Theory and Applications 46 (2013), 1009-1016
Darius Geiß, Rolf Klein, Rainer Penninger, and Günter Rote
-
Advantage in the discrete Voronoi game, Journal of Graph Algorithms and Applications 18 (2014), 439-455
Dániel Gerbner, Viola Mészáros, Dömötör Pálvölgyi, Alexey Pokrovskiy, and Günter Rote
-
On triangulation axes of polygons, Information Processing Letters 115 (2015), 45-51
W. Aigner, F. Aurenhammer, and B. Jüttler
