Geometric Dilation and Halving Distance

Abstract

Let us consider the network of streets of a city represented by a geometric graph G in the plane. The vertices of G represent the crossroads and the edges represent the streets. The latter do not have to be straight line segments, they may be curved. If one wants to drive from a place p to some other place q, normally the length of the shortest path along streets, d_G(p,q), is bigger than the airline distance (Euclidean distance) |pq|. The (relative) DETOUR is defined as delta_G(p,q) := d_G(p,q)/|pq|. The supremum of all these ratios is called the GEOMETRIC DILATION of G. It measures the quality of the network. A small dilation value guarantees that there is no bigger detour between any two points.<br /> Given a finite point set S, we would like to know the smallest possible dilation of any graph that contains the given points on its edges. We call this infimum the DILATION of S and denote it by delta(S).<br /> The main results of this thesis are<br /> - a general upper bound to the dilation of any finite point set S, delta(S)<1.678 <br /> - a lower bound for a specific set P, delta(P)>(1+10^(-11))pi/2, which approximately equals 1.571<br /> In order to achieve these results, we first consider closed curves. Their dilation depends on the HALVING PAIRS, pairs of points which divide the closed curve in two parts of equal length. In particular the distance between the two points is essential, the HALVING DISTANCE. A transformation technique based on halving pairs, the HALVING PAIR TRANSFORMATION, and the curve formed by the midpoints of the halving pairs, the MIDPOINT CURVE, help us to derive lower bounds to dilation. For constructing graphs of small dilation, we use ZINDLER CURVES. These are closed curves of constant halving distance.<br /> To give a structured overview, the mathematical apparatus for deriving the main results of this thesis includes <br /> - upper bound: <br /> * the construction of certain Zindler curves to generate a periodic graph of small dilation <br /> * an embedding argument based on a number theoretical result by Dirichlet <br /> - lower bound: <br /> * the formulation and analysis of the halving pair transformation <br /> * a stability result for the dilation of closed curves based on this transformation and the midpoint curve <br /> * the application of a disk-packing result<br /> In addition, this thesis contains <br /> - a detailed analysis of the dilation of closed curves <br /> - a collection of inequalities, which relate halving distance to other important quantities from convex geometry, and their proofs; including four new inequalities <br /> - the rediscovery of Zindler curves and a compact presentation of their properties <br /> - a proof of the applied disk packing result.

<strong>Geometrische Dilation und Halbierungsabstand</strong><br /> Man kann das von den Straßen einer Stadt gebildete Netzwerk durch einen geometrischen Graphen in der Ebene darstellen. Die Knoten dieses Graphen repräsentieren die Kreuzungen und die Kanten sind die Straßen. Letztere müssen nicht geradlinig sein, sondern können beliebig gekrümmt sein. Wenn man nun von einem Ort p zu einem anderen Ort q fahren möchte, dann ist normalerweise die Länge des kürzesten Pfades über Straßen, d_G(p,q), länger als der Luftlinienabstand (euklidischer Abstand) |pq|. Der (relative) UMWEG (DETOUR) ist definiert als delta_G(p,q) := d_G(p,q)/|pq|. Das Supremum all dieser Brüche wird GEOMETRISCHE DILATION (GEOMETRIC DILATION) von G genannt. Es ist ein Maß für die Qualität des Straßennetzes. Ein kleiner Dilationswert garantiert, dass es keinen größeren Umweg zwischen beliebigen zwei Punkten gibt.<br /> Für eine gegebene endliche Punktmenge S würden wir nun gerne bestimmen, was der kleinste Dilationswert ist, den wir mit einem Graphen erreichen können, der die gegebenen Punkte auf seinen Kanten enthält. Dieses Infimum nennen wir die DILATION von S und schreiben kurz delta(S).<br /> Die Haupt-Ergebnisse dieser Arbeit sind <br /> - eine allgemeine obere Schranke für die Dilation jeder beliebigen endlichen Punktmenge S: delta(S)<1.678 <br /> - eine untere Schranke für eine bestimmte Menge P: delta(P)>(1+10^(-11))pi/2, was ungefähr der Zahl 1.571 entspricht<br /> Um diese Ergebnisse zu erreichen, betrachten wir zunächst geschlossene Kurven. Ihre Dilation hängt von sogenannten HALBIERUNGSPAAREN (HALVING PAIRS) ab. Das sind Punktpaare, die die geschlossene Kurve in zwei Teile gleicher Länge teilen. Besonders der Abstand der beiden Punkte ist von Bedeutung, der HALBIERUNGSABSTAND (HALVING DISTANCE). Eine auf den Halbierungspaaren aufbauende Transformation, die HALBIERUNGSPAARTRANSFORMATION (HALVING PAIR TRANSFORMATION), und die von den Mittelpunkten der Halbierungspaare gebildete Kurve, die MITTELPUNKTKURVE (MIDPOINT CURVE), helfen uns untere Dilationsschranken herzuleiten. Zur Konstruktion von Graphen mit kleiner Dilation benutzen wir ZINDLERKURVEN (ZINDLER CURVES). Dies sind geschlossene Kurven mit konstantem Halbierungspaarabstand.<br /> Die mathematischen Hilfsmittel, mit deren Hilfe wir schließlich die Hauptresultate beweisen, sind unter anderem <br /> - obere Schranke: <br /> * die Konstruktion von bestimmten Zindlerkurven, mit denen periodische Graphen kleiner Dilation gebildet werden können <br /> * ein Einbettungsargument, das einen zahlentheoretischen Satz von Dirichlet benutzt <br /> - untere Schranke: <br /> * die Definition und Analyse der Halbierungspaartransformation <br /> * ein Stabilitätsresultat für die Dilation geschlossener Kurven, das auf dieser Transformation und der Mittelpunktkurve basiert <br /> * die Anwendung eines Kreispackungssatzes<br /> Zusätzlich enthält diese Dissertation <br /> - eine detaillierte Analyse der Dilation geschlossener Kurven <br /> - eine Sammlung von Ungleichungen, die den Halbierungsabstand zu anderen wichtigen Größen der Konvexgeometrie in Beziehung setzen, und ihre Beweise; inklusive vier neuer Ungleichungen <br /> - die Wiederentdeckung von Zindlerkurven und eine kompakte Darstellung ihrer Eigenschaften <br /> - einen Beweis des angewendeten Kreispackungssatzes.