Constructing Approximate Shortest Path Maps in Three Dimensions

DOI10.1137/S0097539797325223zbMath0943.68169MaRDI QIDQ4268702

Sariel Har-Peled

Publication date: 28 October 1999

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

zbMATH Keywords

approximation algorithmsVoronoi diagramsEuclidean shortest paths

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Three-dimensional polytopes (52B10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Related Items (9)

An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ An approximation algorithm for computing shortest paths in weighted 3-d domains ⋮ Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ A survey of geodesic paths on 3D surfaces ⋮ An optimal-time algorithm for shortest paths on a convex polytope in three dimensions ⋮ Approximation algorithms for shortest descending paths in terrains ⋮ Approximating Minimization Diagrams and Generalized Proximity Search

This page was built for publication: Constructing Approximate Shortest Path Maps in Three Dimensions