Improved Spanning and Routing Ratios on Geometric Graphs

1 introduction 5 1.1 Navigation on Geometric Graphs 5 1.2 Classes of Geometric Graphs Considered 6 1.2.1 Θ k -Graphs and Y k -Graphs 6 1.2.2Delaunay Graphs 7 1.3 Previous Work 8 2 improved routing on the delaunay triangulation 14 2.1 Introduction 14 2.2 The MixedChordArc Algorithm 16 2.3 Bounding |P s, t | in a Balanced Configuration 18 2.3.1 Analysis Technique 19 2.3.2Proof of Lemma 2.3.4 22 2.3.3Proof of Lemma 2.3.3 23 2.4 Bounding P s, t in the General Case 24 2.5 Conclusion and Future Work 28 2.6 A Trace of MixedChordArc and an Illustration of the Proof of Theorem 2.2.1 29 2.7 Proof of Lemma 2.4.2 35 2.8 Proofs of Lemmas 2.3.8 and 2.3.9 -Analyzing Φ(C i-1 , C i ) 38 2.8.1 Analyzing dΦ(C i-1 ,C i ) dx(c i ) 40 2.8.2 Simplifying dΦ(C i-1 ,C i ) dx(c i ) contents 2 4 the spanning ratio of convex polyhedra whose vertices are on a sphere 85 4.1 Chains of Disks 86 4.2 Main Theorem 87 4.3 Conclusion 90 5 improved spanning ratio on theta-five 92 5.1 Introduction 92 5.2 Preliminaries 94 5.3 General Triangles T 1 and T 2 97 5.4 Analysis of |P a, b | 100 5.4.1 Vertex c in P 5 103 5.5 Down to K ≥ 5.70 107 5.5.1 Lemma 5.5.1,Φ ≤ Φ 1 109 5.5.2Lemma 5.5.2,Φ 1 ≤ Φ 2 110 5.6 Conclusion 111 6 conclusion 114 P R E FA C EThis thesis is in "integrated article format" in which each chapter is based on published papers, conference proceedings, or papers awaiting publication.• Chapter 2 considers competitive online local routing on the Delaunay triangulation.These results appeared in the proceedings of the European Symposium on Algorithms (ESA 18)[1].• Chapter 3 considers competitive online local routing on the Θ 4 -graph.These results appeared in the proceedings of the Symposium on Discrete Algorithms (SODA 19)[2].• Chapter 4 improves the spanning ratio of the convex hull of points on a sphere.This was part of a result published in the Journal of Computational Geometry (JoCG) [3].• Chapter 5 improves the spanning ratio of the Θ 5 -graph.It is awaiting publication.Metric Lower Bound Upper Bound L 1 , L ∞ (Square) ≈ 2.61[7] ≈ 2.61[7] (tight) TD (Equilateral triangles) 2[16] 2[16] L 2 (Circles) 1.5932[28] 1.998[27] Rectangles Open OpenΘ-graphs were introduced by Keil and Gutwin[21, 22] and Clarkson[17] as an alternative to Yao-graphs since they were easier to compute.A spanning ratio of 1/(cos θsin θ) is proven in both articles.Ruppert and Seidel[26] improved this to 1/(1 -2 sin(θ/2)).Chew's[15] paper on the spanning ratio of the L 1 -Delaunay triangulation is also a local routing algorithm on that same graph.Thus it simultaneously provides a bound on the routing ratio of the L 1 -Delaunay triangulation of √ 10.Bose and Morin [12] show that there are no 1-local memoryless routing algorithms that will work on any arbitrary graph.This implies that we must pair routing algorithms with particular classes of geometric graphs in order to route competitively.For example, in greedy routing, the message at vertex x moves to the neighbour y of x such that the distance |yt| is minimized, i.e., the neighbour of x that is closest to t.In Figures 1.3a and 1.3b we see examples of graphs where greedy routing cycles between two and three vertices respectively.However, greedy routing will always find the destination on the L 2 -Delaunay triangulation.They also give a competitive routing algorithm for the L 2 -Delaunay triangulation.However, they show that there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations.Bose and Morin[13] provide a competitive local routing algorithm that works on triangulations that have the diamond property.This includes such graphs as the L 2 -Delaunay triangulation, the greedy triangulation, and the minimum weight triangulation.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.