Let G be an embedded planar graph whose edges may be curves. For
two arbitrary points of G, we can compare the length of the
shortest path in G connecting them against their Euclidean
distance. The supremum of all these ratios is called the geometric dilation of G. Given a finite point set, we would
like to know the smallest possible dilation of any graph that
contains the given points. In this paper we prove that a dilation
of 1.678 is always sufficient, and that π/2 = 1.570... is
sometimes necessary in order to accommodate a finite set of
points.
Computational geometry - Detour - Dilation - Graph - Network - Spanner - Stretch factor - Transportation network