 |
 |
 |
Conference papers
Efficiently Navigating a Random Delaunay Triangulation
Abstract : Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. Whilst many algorithms have been proposed, very little theoretical analysis is available for the properties of the paths generated or the computational resources required to generate them. In this work, we propose and analyse a new planar navigation algorithm for the Delaunay triangulation. We then demonstrate a number of strong theoretical guarantees for the algorithm when it is applied to a random set of points in a convex region.
Cited literature [22 references]
https://hal.inria.fr/hal-01018174
Contributor : Ross Hemsley <>
Submitted on : Thursday, July 3, 2014 - 5:17:39 PM
Last modification on : Monday, December 14, 2020 - 5:16:20 PM
Long-term archiving on: : Friday, October 3, 2014 - 11:57:14 AM
Contributor : Ross Hemsley <>
Submitted on : Thursday, July 3, 2014 - 5:17:39 PM
Last modification on : Monday, December 14, 2020 - 5:16:20 PM
Long-term archiving on: : Friday, October 3, 2014 - 11:57:14 AM
Files
aofa.pdf
Publisher files allowed on an open archive