An optimal-time algorithm for shortest paths on realistic polyhedra

DOI10.1007/s00454-009-9136-8zbMath1191.68769OpenAlexW2090626328MaRDI QIDQ848859

Yevgeny Schreiber

Publication date: 23 February 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9136-8

zbMATH Keywords

wavefrontterrainshortest path mapconforming subdivisioncontinuous Dijkstrarealistic polyhedral surface

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces ⋮ Approximating geodesic distances on 2-manifolds in image \(\mathbb R^3\) ⋮ An improved algorithm for the shortest descending path on a convex terrain ⋮ Tracing compressed curves in triangulated surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Motion planning in environments with low obstacle density
• Range searching in low-density environments
• On fat partitioning, fat covering and the union size of polygons
• Linear size binary space partitions for uncluttered scenes
• Storing the subdivision of a polyhedral surface
• The complexity of the free space for motion planning amidst fat obstacles
• Realistic input models for geometric algorithms
• Computing depth orders for fat objects and related problems
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• Approximating Shortest Paths on a Nonconvex Polyhedron
• Efficient computation of geodesic shortest paths
• The Discrete Geodesic Problem
• Shortest paths on realistic polyhedra
• On Shortest Paths in Polyhedral Spaces
• On Shortest Paths Amidst Convex Polyhedra
• Constructing Approximate Shortest Path Maps in Three Dimensions
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Approximating shortest paths on a convex polytope in three dimensions
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• Fundamentals of Computation Theory
• Approximating shortest paths on weighted polyhedral surfaces

This page was built for publication: An optimal-time algorithm for shortest paths on realistic polyhedra