Skip to Main content Skip to Navigation
Journal articles

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

Prosenjit Bose 1 Jean-Lou de Carufel 1 Olivier Devillers 2, 3
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 $\Theta_6$ graph and the half-$\Theta_6$ graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex $s$ and a target vertex $t$ in the $\Theta_6$ graph (resp. half-$\Theta_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 factor for the $\Theta_6$ graph and half-$\Theta_6$ graph defined on a Poisson point process. For the $\Theta_6$ graph, our online routing algorithm has an expected routing factor of $1.161$ when $s$ and $t$ are random. The $routing$ $factor$ is the length of the route between $s$ and $t$ produced by our algorithm divided by the Euclidean distance between $s$ and $t$. Moreover, our routing algorithm has a maximum expected routing factor of $1.22$, where the maximum is for fixed $s$ and $t$ and all other points are random. This is much better than the worst-case routing ratio of $2$. The $routing$ $ratio$ is the maximum routing factor among all pairs of points. For the half-$\Theta_6$ graph, our memoryless online routing algorithm has an expected routing factor of $1.43$ and a maximum expected routing factor of $1.58$. Our online routing algorithm that uses a constant amount of additional memory, has an expected routing factor of $1.34$ and a maximum expected routing factor 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 factor that is much better than their worst-case routing ratio of $2.89$.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download


https://hal.inria.fr/hal-02922660
Contributor : Olivier Devillers <>
Submitted on : Wednesday, August 26, 2020 - 1:57:35 PM
Last modification on : Tuesday, February 23, 2021 - 8:56:05 AM
Long-term archiving on: : Friday, November 27, 2020 - 12:45:41 PM

Identifiers

Collections

Citation

Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers. Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2020, 11 (1), pp.212 - 234. ⟨10.20382/jocg.v11i1a9⟩. ⟨hal-02922660⟩

Share

Metrics

Record views

58

Files downloads

186