HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs

3 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. For the Θ6-graph, our online routing algorithm has an expected routing ratio of 1.161 (when s and t random) and a maximum expected routing ratio of 1.22 (maximum for fixed s and t where all other points are random), much better than the worst-case routing ratio of 2. For the half-Θ6-graph, our memoryless online routing algorithm has an expected routing ratio of 1.43 and a maximum expected routing ratio of 1.58. Our online routing algorithm that uses a constant amount of additional memory has an expected routing ratio of 1.34 and a maximum expected routing ratio of 1.40. The additional memory is only used to remember the coordinates of the starting point of the route. Both of these algorithms have an expected routing ratio that is much better than their worst-case routing ratio of 2.89.
Document type :
Reports

https://hal.inria.fr/hal-02338733
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, November 29, 2019 - 8:48:40 AM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM

### Files

thetarouting.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-02338733, version 2
• ARXIV : 1910.14289

### Citation

Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers. Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs. [Research Report] INRIA. 2019, pp.18. ⟨hal-02338733v2⟩

Record views