The Discrete Geodesic Problem
From MaRDI portal
Publication:3028357
DOI10.1137/0216045zbMath0625.68051OpenAlexW2108567935MaRDI QIDQ3028357
David M. Mount, Joseph S. B. Mitchell, Christos H. Papadimitriou
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216045
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Discrete mathematics in relation to computer science (68R99)
Related Items (79)
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces ⋮ Between shapes, using the Hausdorff distance ⋮ SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM ⋮ A numerical simulation of neural fields on curved geometries ⋮ Space complexity of exact discrete geodesic algorithms on regular triangulations ⋮ Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing ⋮ An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ Shortest Path Problems on a Polyhedral Surface ⋮ A Pseudopolynomial Algorithm for Alexandrov’s Theorem ⋮ Curve matching, time warping, and light fields: New algorithms for computing similarity between curves ⋮ A new algorithm for shortest paths among obstacles in the plane ⋮ Geodesics on the regular tetrahedron and the cube ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Fast geodesics computation with the phase flow method ⋮ On the Optimality of Shape and Data Representation in the Spectral Domain ⋮ An algorithmic approach to some problems in terrain navigation ⋮ Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon ⋮ Shortest monotone descent path problem in polyhedral terrain ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models ⋮ Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\) ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ On different topological classes of spherical geodesic paths and circles in \(\mathbb{Z}^3\) ⋮ Shortest Journeys in Directed Temporal Graphs ⋮ An Extended MMP Algorithm: Wavefront and Cut-Locus on a Convex Polyhedron ⋮ Computing the Riemannian center of mass on meshes ⋮ Approximating generalized distance functions on weighted triangulated surfaces with applications ⋮ A quasi-meshfree method for constructing boundary-aware reproducing bases on geometrically complex domains using manifold geodesics ⋮ Discrete exterior calculus for meshes with concyclic polygons ⋮ Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves ⋮ An improved algorithm for the shortest descending path on a convex terrain ⋮ Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER ⋮ Unnamed Item ⋮ Near optimal algorithm for the shortest descending path on the surface of a convex terrain ⋮ On maximum flows in polyhedral domains ⋮ Computing approximately shortest descending paths on convex terrains via multiple shooting ⋮ Geodesics on point clouds ⋮ A survey of geodesic paths on 3D surfaces ⋮ The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains ⋮ Visibility graphs and obstacle-avoiding shortest paths ⋮ Shortest path problems on a polyhedral surface ⋮ Unnamed Item ⋮ Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding ⋮ On realistic terrains ⋮ Splitting (complicated) surfaces is hard ⋮ Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Discrete Lagrangian algorithm for finding geodesics on triangular meshes ⋮ Random field simulation over curved surfaces: applications to computational structural mechanics ⋮ Multiple shooting approach for computing approximately shortest paths on convex polytopes ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ Topological analysis of voxelized objects by discrete geodesic Reeb graph ⋮ An optimal-time algorithm for shortest paths on a convex polytope in three dimensions ⋮ Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings ⋮ Parallel chen-han (PCH) algorithm for discrete geodesics ⋮ Approximation algorithms for shortest descending paths in terrains ⋮ Craniofacial reconstruction evaluation by geodesic network ⋮ On the number of shortest descending paths on the surface of a convex terrain ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ Higher-order Voronoi diagrams on triangulated surfaces ⋮ Time-minimal paths amidst moving obstacles in three dimensions ⋮ Designing approximation minimal parametric surfaces with geodesics ⋮ SKEW VORONOI DIAGRAMS ⋮ Pursuit evasion on polyhedral surfaces ⋮ How to walk your dog in the mountains with no magic leash ⋮ Computing generalized higher-order Voronoi diagrams on triangulated surfaces ⋮ Ordered line integral methods for solving the eikonal equation ⋮ DIG: Discrete Iso-contour Geodesics for Topological Analysis of Voxelized Objects ⋮ Thaw: A Tool for Approximating Cut Loci on a Triangulation of a Surface ⋮ Shortest polygonal paths in space ⋮ Shortest descending paths through given faces ⋮ A Geometrical Method for Low-Dimensional Representations of Simulations ⋮ Storing the subdivision of a polyhedral surface ⋮ Wrapping spheres with flat paper ⋮ The transportation metric and related problems ⋮ Ununfoldable polyhedra with convex faces
This page was built for publication: The Discrete Geodesic Problem
