Minimum Dilation Triangulations

Christian Knauer
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: [last name]@mi.fu-berlin.de

Wolfgang Mulzer
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: [last name]@mi.fu-berlin.de

Report B 05-06
April 2005

Abstract
Given a planar graph $G$, the graph theoretic dilation of $G$ is defined as the maximum ratio of the shortest-path distance and the Euclidean distance between any two vertices of $G$. Given a planar point set $S$, the graph theoretic dilation of $S$ is the minimum graph theoretic dilation that any triangulation of $S$ can achieve. We study the graph theoretic dilation of the regular $n$-gon. In particular, we compute a simple lower bound for the graph theoretic dilation of the regular $n$-gon and use this bound in order to derive an efficient approximation algorithm that computes a triangulation whose graph theoretic dilation is within a factor of $1+O\left(1/\sqrt{\log n}\right)$ of the optimum. Furthermore, we demonstrate how the general concept of exclusion regions applies to minimum dilation triangulations.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-05-06.ps.gz