Upper and lower bounds for online routing on Delaunay triangulations
From MaRDI portal
Publication:2408218
DOI10.1007/S00454-016-9842-YzbMath1378.68156OpenAlexW4392020555MaRDI QIDQ2408218
Jean-Lou De Carufel, André van Renssen, Prosenjit Bose, Nicolas Bonichon, Ljubomir Perković
Publication date: 10 October 2017
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://hal.science/hal-01412046
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Signed and weighted graphs (05C22) Online algorithms; streaming algorithms (68W27)
Related Items (7)
Routing on heavy-path WSPD-spanners ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Improved routing on the Delaunay triangulation ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Unnamed Item ⋮ Routing on heavy path WSPD spanners ⋮ Greedy routing and the algorithmic small-world phenomenon
Cites Work
- A note on two problems in connexion with graphs
- On plane geometric spanners: a survey and open problems
- Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations
- Delaunay graphs are almost as good as complete graphs
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- There are planar graphs almost as good as the complete graph
- Efficiently navigating a random Delaunay triangulation
- The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
- Competitive Online Routing on Delaunay Triangulations
- Geometric Spanner Networks
- Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
- Online Routing in Triangulations
- Embedded Robotics
This page was built for publication: Upper and lower bounds for online routing on Delaunay triangulations
