Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon

DOI10.1016/j.tcs.2004.01.014zbMath1075.68090OpenAlexW2047629658MaRDI QIDQ598213

Dmitri Burago, Dima Yu. Grigoriev, Anatol Slissenko

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.01.014

zbMATH Keywords

Shortest pathSkew lines problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (3)

Polyhedral Finsler spaces with locally unique geodesics ⋮ A survey of geodesic paths on 3D surfaces ⋮ On intrinsic geometry of surfaces in normed spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometry IV. Non-regular Riemannian geometry. Transl. from the Russian by E. Primrose
• An algorithm for shortest-path motion in three dimensions
• Hard balls gas and Alexandrov spaces of curvature bounded above
• Search for shortest path around semialgebraic obstacles in the plane
• The Euclidean traveling salesman problem is NP-complete
• Uniform estimates on the number of collisions in semi-dispersing billiards
• The Discrete Geodesic Problem
• On Shortest Paths in Polyhedral Spaces
• Constructing Approximate Shortest Path Maps in Three Dimensions
• The weighted region problem
• Approximate Euclidean Shortest Paths in 3-Space
• Approximating shortest paths on a convex polytope in three dimensions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon