Adrian Dumitrescu, Ansgar Grüne, and Günter Rote:
On the geometric dilation of curves and point sets
Manuscript, July 2004, 14 pages, submitted for publication.
Abstract
The detour between two points u
and v (on edges or vertices)
of an embedded
planar graph whose edges are curves is the ratio between the shortest
path in in the graph between u
and v and their Euclidean
distance. The
maximum detour over all pairs of points is called the geometric
dilation.
Ebbers-Baumann, Grüne and Klein have shown that every finite point
set is
contained in a planar graph whose geometric dilation is at most 1.678,
and
some point sets require graphs with dilation >=pi/2=1.57... We prove
a
stronger lower bound of (1+10-11)pi/2 by relating graphs
with small dilation to
a problem of packing and covering the plane by circular disks.
Last update: July 8, 2004.