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.


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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: July 8, 2004.