An optimal-time algorithm for shortest paths on realistic polyhedra

DOI10.1007/S00454-009-9136-8MaRDI QIDQ848859zbMATH OpenOpenAlexFDO

Authors 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

terrainwavefrontshortest path mapconforming subdivisioncontinuous Dijkstrarealistic polyhedral surface

Mathematics Subject Classification ID

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

Recommendations

• Shortest paths on realistic polyhedra
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• On Shortest Paths in Polyhedral Spaces

Cites work

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

Cited in

(8)

• Time and space efficient algorithms for shortest paths between convex polygons
• An improved algorithm for the shortest descending path on a convex terrain
• Tracing compressed curves in triangulated surfaces
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• Shortest paths on realistic polyhedra
• Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• Approximating geodesic distances on 2-manifolds in image \(\mathbb R^3\)

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

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