Efficient computation of geodesic shortest paths

DOI10.1145/301250.301449MaRDI QIDQ2819608zbMATH OpenOpenAlexFDO

Authors Sanjiv Kapoor

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301449

Mathematics Subject Classification ID

Three-dimensional polytopes (52B10) Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 1302178
• Finding Shortest Paths With Computational Geometry
• Approximation algorithms for geometric shortest path problems
• Fundamentals of Computation Theory
• Geometric speed-up techniques for finding shortest paths in large sparse graphs
• Approximating geometric bottleneck shortest paths
• scientific article; zbMATH DE number 1962800
• Geometric k Shortest Paths
• scientific article; zbMATH DE number 1424303
• Geometric containers for efficient shortest-path computation

Cited in

(39)

• Shortest curves in planar regions with curved boundary
• Designing approximation minimal parametric surfaces with geodesics
• Shortest path geometric rounding
• Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
• Routing among convex polygonal obstacles in the plane
• Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
• Curve matching, time warping, and light fields: New algorithms for computing similarity between curves
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings
• Space complexity of exact discrete geodesic algorithms on regular triangulations
• Constructing a minimum path on a polyhedral surface in R^3
• The Discrete Geodesic Problem
• Approximation algorithms for geometric shortest path problems
• An Efficient Algorithm for Shortest Path in Three Dimensions With Polyhedral Obstacles
• scientific article; zbMATH DE number 5734722 (Why is no real title available?)
• scientific article; zbMATH DE number 3907791 (Why is no real title available?)
• Computing geodesic paths on manifolds
• Approximating generalized distance functions on weighted triangulated surfaces with applications
• scientific article; zbMATH DE number 727953 (Why is no real title available?)
• Finding shortest paths in a sequence of triangles in 3D by the planar unfolding
• Finding Shortest Paths With Computational Geometry
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• Precision-Sensitive Euclidean Shortest Path in 3-Space
• Drawing Shortest Paths in Geodetic Graphs
• Drawing Shortest Paths in Geodetic Graphs
• Geometric k Shortest Paths
• Thaw: A Tool for Approximating Cut Loci on a Triangulation of a Surface
• Variational, Geometric, and Level Set Methods in Computer Vision
• Fundamentals of Computation Theory
• Inapproximability of finding maximum hidden sets on polygons and terrains
• A survey of geodesic paths on 3D surfaces
• Efficient exact enumeration of single-source geodesics on a non-convex polyhedron
• Routing among convex polygonal obstacles in the plane
• The funnel tree algorithm for finding shortest paths on polyhedral surfaces
• Computing generalized higher-order Voronoi diagrams on triangulated surfaces
• Routing among convex polygonal obstacles in the plane using a simplified domain
• An optimal-time algorithm for shortest paths on realistic polyhedra
• Shortest monotone descent path problem in polyhedral terrain
• On realistic terrains

This page was built for publication: Efficient computation of geodesic shortest paths

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