# 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