An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
From MaRDI portal
Publication:2482203
DOI10.1007/s00454-007-9031-0zbMath1138.68060OpenAlexW2132432991MaRDI QIDQ2482203
Yevgeny Schreiber, Micha Sharir
Publication date: 16 April 2008
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-007-9031-0
Analysis of algorithms (68W40) Computational aspects related to convexity (52B55) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (13)
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces ⋮ An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ Shortest Path Problems on a Polyhedral Surface ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ An improved algorithm for the shortest descending path on a convex terrain ⋮ Near optimal algorithm for the shortest descending path on the surface of a convex terrain ⋮ A survey of geodesic paths on 3D surfaces ⋮ Shortest path problems on a polyhedral surface ⋮ An optimal-time algorithm for shortest paths on a convex polytope in three dimensions ⋮ Star unfolding convex polyhedra via quasigeodesic loops ⋮ Voronoi game on polygons ⋮ Tracing compressed curves in triangulated surfaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Nonoverlap of the star unfolding
- Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
- Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
- Storing the subdivision of a polyhedral surface
- Edge-unfolding nested polyhedral bands
- An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
- Efficient computation of geodesic shortest paths
- The Discrete Geodesic Problem
- Shortest paths on realistic polyhedra
- Optimal Point Location in a Monotone Subdivision
- On Shortest Paths in Polyhedral Spaces
- On Shortest Paths Amidst Convex Polyhedra
- Optimal Search in Planar Subdivisions
- Constructing Approximate Shortest Path Maps in Three Dimensions
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Two-Dimensional and Three-Dimensional Point Location in Rectangular Subdivisions
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Star Unfolding of a Polytope with Applications
- Approximating shortest paths on a convex polytope in three dimensions
- SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
- An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
- 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 a convex polytope in three dimensions
