IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION

DOI10.1142/S0218195912500161MaRDI QIDQ5300011zbMATH OpenOpenAlexFDO

Authors Manuel Abellanas, Mercè Claverol, Gregorio Hernández, Ferran Hurtado, Vera Sacristán, Maria Saumell, Rodrigo I. Silveira

Publication date 24 June 2013

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

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

zbMATH Keywords

Delaunay triangulationdilationshortest path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Improved routing on the Delaunay triangulation
• Improved routing on the Delaunay triangulation
• Self-improving algorithms for delaunay triangulations
• Approximate shortest paths in simple polyhedra
• An improvement of Dijkstra's method for finding a shortest path in a graph
• Optimal shortest path queries in a simple polygon
• scientific article; zbMATH DE number 2066953
• Fundamentals of Computation Theory
• An optimal algorithm for realizing a Delaunay triangulation
• Triangulation refinement and approximate shortest paths in weighted regions

Cites work

• A sweepline algorithm for Voronoi diagrams
• Algorithms for Reporting and Counting Geometric Intersections
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Augmenting the connectivity of outerplanar graphs
• Augmenting the connectivity of planar and geometric graphs
• Connectivity augmentation in plane straight line graphs
• Delaunay graphs are almost as good as complete graphs
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Online Routing in Triangulations
• Transitions in geometric minimum spanning trees

Cited in

(1)

• Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path

This page was built for publication: IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300011)