Memoryless routing in convex subdivisions: random walks are optimal

DOI10.1016/j.comgeo.2011.12.005zbMath1259.65038arXiv0911.2484OpenAlexW2122684646MaRDI QIDQ419369

Dan Chen, Vida Dujmović, Pat Morin, Luc P. Devroye

Publication date: 18 May 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.2484

zbMATH Keywords

lower boundsrandom walkgeometric routingconvex subdivision schemememoryless routing algorithmrandom-compass algorithm

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (5)

Bounding the locality of distributed routing algorithms ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Local Routing in Convex Subdivisions ⋮ Efficiently navigating a random Delaunay triangulation

Cites Work

• Unnamed Item
• Unnamed Item
• Undirected ST-connectivity in log-space
• Online Routing in Triangulations
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Random walks on random trees

This page was built for publication: Memoryless routing in convex subdivisions: random walks are optimal