hide
Free keywords:
-
Abstract:
Consider a plane graph G, drawn with straight lines. For every pair a,b of
vertices of G, we compare the shortest-path distance between a and b in G (with
Euclidean edge lengths) to their actual distance in the plane. The worst-case
ratio of these two values, for all pairs of points, is called the dilation of G
. All finite plane graphs of dilation 1 have been classified. They are closely
related to the following iterative procedure. For a given point set P ⊆ R2, we
connect every pair of points in P by a line segment and then add to P all those
points where two such line segments cross. Repeating this process infinitely
often, yields a limit point set P∞⊇P. This limit set P∞ is finite if and only
if P is contained in the vertex set of a triangulation of dilation 1.The main
result of this paper is the following gap theorem: For any finite point set P
in the plane for which P∞ is infinite, there exists a threshold λ > 1 such that
P is not contained in the vertex set of any finite plane graph of dilation at
most λ. As a first ingredient to our proof, we show that such an infinite P∞
must lie dense in a certain region of the plane. In the second, more difficult
part, we then construct a concrete point set P0 such that any planar graph that
contains this set amongst its vertices must have a dilation larger than
1.0000047.
