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.