Skip to Main content Skip to Navigation

Expected Complexity of Routing in $Θ 6$ and Half-$Θ 6$ Graphs

Prosenjit Bose 1 Jean-Lou de Carufel 1 Olivier Devillers 2
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We study online routing algorithms on the $Θ 6$-graph and the half-$Θ 6$-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the $Θ 6$-graph (resp. half-Θ 6-graph), there exists a deterministic online routing algorithm that finds a path from s to t whose length is at most 2 st (resp. 2.89 st) which is optimal in the worst case [Bose et al., siam J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the $Θ 6$-graph and half-$Θ 6$-graph defined on a Poisson point process.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Friday, February 14, 2020 - 3:18:43 PM
Last modification on : Wednesday, March 18, 2020 - 3:28:17 PM


Files produced by the author(s)


  • HAL Id : hal-02479502, version 1



Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers. Expected Complexity of Routing in $Θ 6$ and Half-$Θ 6$ Graphs. EuroCG 2020 - 36th European Workshop on Computational Geometry, Mar 2020, Würzburg, Germany. ⟨hal-02479502⟩



Record views


Files downloads