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.)


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.

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