Online Routing in Triangulations

DOI10.1137/S0097539700369387zbMath1061.65014OpenAlexW1991764368MaRDI QIDQ4651500

Pat Morin, Prosenjit Bose

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700369387

zbMATH Keywords

numerical exampleshortest pathonline algorithmsroutingspanning pathDelaunay triangulations

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (26)

On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Routing on heavy-path WSPD-spanners ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Competitive online routing in geometric graphs ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ Bounding the locality of distributed routing algorithms ⋮ Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION ⋮ Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ A general framework for searching on a line ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Memoryless routing in convex subdivisions: random walks are optimal ⋮ Forwarding via checkpoints: geographic routing on always-on sensors ⋮ Local Routing in Convex Subdivisions ⋮ Minimum weight convex Steiner partitions ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs ⋮ Efficiently navigating a random Delaunay triangulation ⋮ A General Framework for Searching on a Line ⋮ Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Unnamed Item

This page was built for publication: Online Routing in Triangulations