1. Adrian Dumitrescu, Ansgar Grüne, and Günter Rote:
Improved lower bound on the geometric dilation of point sets
In: Abstracts of the 21st European Workshop on Computational
Eindhoven, March 2005, pp. 37-40.
2. Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne,
Rolf Klein, and Günter Rote:
On geometric dilation and halving chords
In: Proceedings of the Workshop on Algorithms and Data
Structures (WADS 2005), Waterloo, Canada, August 2005, Editors:
López-Ortiz, Frank Dehne, and Jörg-Rüdiger Sack.
Computer Science, 3608, Springer-Verlag, 2005, pp. 244-255.
3. Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne,
Rolf Klein, and
On the geometric dilation of closed curves, graphs, and point sets
Computational Geometry, Theory and Applications 36 (2006),
(This is a detailed and combined version of 1 and
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
maximum detour over all pairs of points is called the geometric
Ebbers-Baumann, Grüne and Klein have shown that every finite point
contained in a planar graph whose geometric dilation is at most 1.678,
some point sets require graphs with dilation ≥pi/2=1.57... We
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.
The proof relies on halving pairs, pairs of points dividing a given
curve C in two parts of equal length, and their minimum and
distances h and H. Additionally, we analyze
distance (h=H), examine the relation of h to
quantities and geometric problems (like Ulam's floating body problem)
and prove some new dilation bounds.
Last update: January 8, 2008.