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