HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_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 metadata

Cited literature [12 references]  Display  Hide  Download


https://hal.inria.fr/hal-02479502
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, February 14, 2020 - 3:18:43 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM
Long-term archiving on: : Friday, May 15, 2020 - 4:15:17 PM

Files

EuroCG-1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02479502, version 1

Collections

Citation

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

Share

Metrics

Record views

68

Files downloads

41