Competitive online routing in geometric graphs

DOI10.1016/j.tcs.2004.05.019zbMath1073.68059OpenAlexW2119251691MaRDI QIDQ1887089

Pat Morin, Prosenjit Bose

Publication date: 23 November 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.05.019

zbMATH Keywords

Delaunay triangulationPlanar graphGeometric graphCompetitive routingGood polygonGreedy triangulationMinimum weight triangulationOnline routingSpannerSpanning ratio

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Bounding the locality of distributed routing algorithms ⋮ Routing among convex polygonal obstacles in the plane ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ Routing in polygonal domains ⋮ A GENERAL APPROXIMATION ALGORITHM FOR PLANAR MAPS WITH APPLICATIONS ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Construction and Local Routing for Angle-Monotone Graphs ⋮ Augmenting the connectivity of geometric graphs ⋮ Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations ⋮ Local Routing in Convex Subdivisions ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ Minimum weight convex Steiner partitions ⋮ Efficiently navigating a random Delaunay triangulation ⋮ Constrained routing between non-visible vertices ⋮ Competitive Searching for a Line on a Line Arrangement.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Searching in the plane
• Shortest paths without a map
• Constructing competitive tours from local information
• Online Routing in Triangulations
• ONLINE ROUTING IN CONVEX SUBDIVISIONS