Paul Seiferth

Computational Aspects of Triangulations with Constant Dilation

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 26.11.2012
Homepage des Autors:


Let $G$ be a plane geometric graph. For two distinct vertices $u,v$ of $G$ we can consider the ratio between the length $d_G(u,v)$ of the shortest path and the Euclidean distance $|u,v|$ between $u$ and $v$. The dilation of $G$ is the maximum over all these ratios, i.e. $\max_{u,v\in V(G)}\frac{d_G(u,v)}{|u,v|}$.

The aim of this Master Thesis is to examine the geometric properties of triangulations that have bounded dilation and to utilize them in an algorithmic way. Krznaric and Levcopoulos showed that given the Delaunay triangulation for a planar point set $S$ we can compute a hierarchical clustering for $S$ in linear time. We present a similar algorithm that does not insist on the Delaunay triangulation but uses triangulations that have constant dilation. Unfortunately, when analyzing the running time it turned out that the running time of the algorithm is not linear. We identified two properties that are necessary to achieve linear running time. It is left as an open question what kind of triangulations, except for the Delaunay triangulation, fulfill these properties. Furthermore, we state additional properties of triangulations with constant dilation that were encountered during the analysis of the algorithm.