## 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
Geometry,
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:
Alexandro
López-Ortiz, Frank Dehne, and Jörg-Rüdiger Sack.
Lecture
Notes in
Computer Science, 3608, Springer-Verlag, 2005, pp. 244-255.**
*doi:10.1007/11534273_22
## 3. Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne,
Rolf Klein, and
Günter Rote:

# On the geometric dilation of closed curves, graphs, and point sets

*Computational Geometry, Theory and Applications 36 (2006),
16-38. arXiv:math/0407135
[math.MG]. *doi:10.1016/j.comgeo.2005.07.004*
*(This is a detailed and combined version of 1 and
2.)
### 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.
The proof relies on halving pairs, pairs of points dividing a given
closed
curve *C* in two parts of equal length, and their minimum and
maximum
distances *h* and *H*. Additionally, we analyze
curves of
constant halving
distance (*h*=*H*), examine the relation of *h* to
other geometric
quantities and geometric problems (like Ulam's floating body problem)
and prove some new dilation bounds.

Last update: January 8, 2008.