ONLINE ROUTING IN CONVEX SUBDIVISIONS

DOI10.1142/S021819590200089XzbMath1152.68478OpenAlexW2171151410MaRDI QIDQ4818562

Pat Morin, Rudolf Fleischer, Erik D. Demaine, J. Ian Munro, Andrej Brodnik, Svante Carlsson, Prosenjit Bose, Alejandro López-Ortiz

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s021819590200089x

zbMATH Keywords

online algorithmscomputational geometryroutingoblivious algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Competitive online routing in geometric graphs ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ Bounding the locality of distributed routing algorithms ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ Memoryless routing in convex subdivisions: random walks are optimal ⋮ Local Routing in Convex Subdivisions ⋮ Minimum weight convex Steiner partitions ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ Efficiently navigating a random Delaunay triangulation ⋮ On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Local routing in a tree metric \(1\)-spanner ⋮ Unnamed Item

Cites Work

• Shortest paths without a map
• Constructing competitive tours from local information
• Triangulations intersect nicely
• An efficient algorithm for determining the convex hull of a finite planar set

This page was built for publication: ONLINE ROUTING IN CONVEX SUBDIVISIONS