2020
Expected complexity of routing in Θ6 and halfΘ6 graphs
Publication
Publication
Journal of Computational Geometry , Volume 11  Issue 1 p. 212 234
We study online routing algorithms on the Θ6graph and the halfΘ6graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the Θ6graph (resp. halfΘ6graph), 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 Θ6graph and halfΘ6graph defined on a Poisson point process. For the Θ6graph, 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 worstcase routing ratio of 2. The routing ratio is the maximum routing factor among all pairs of points. For the halfΘ6graph, 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 worstcase routing ratio of 2.89.
Additional Metadata  

Journal of Computational Geometry  
Organisation  School of Computer Science 
Bose, P, De Carufel, J.L. (JeanLou), & Devillers, O. (Olivier). (2020). Expected complexity of routing in Θ6 and halfΘ6 graphs. Journal of Computational Geometry, 11(1), 212–234.
