Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
Given a convex polytope \(P\) with \(n\) edges in Euclidean 3-space, the author presents a relatively simple algorithm that preprocesses \(P\) in \(O(n)\) time, such that, given any two points \(s,t\in\partial P\) and a parameter \(0<\varepsilon\leq 1\), it computes, in \(O((\log n)/\varepsilon^{1.5}+1/\varepsilon^3)\) time, a distance \(\Delta_P(s,t)\) such that \(d_P(s,t)\leq\Delta_P(s,t)\leq (1+\varepsilon)d_P(s,t)\), where \(d_P(s,t)\) is the length of the shortest path between \(s\) and \(t\) on \(\partial P\). The algorithm also produces a polygonal path with \(O(1/\varepsilon^{1.5})\) segments that avoids the interior of \(P\) and has length \(\Delta_P(s,t)\). In contrast, the fastest known algorithm for computing a data-structure that supports queries of computing the length of the exact shortest path between any pair of points on \(\partial P\) is due to \textit{P. K. Agarwal, B. Aronov, J. O'Rourke} and \textit{C. Schevon} [SIAM J. Comput. 26, No. 6, 1689-1713 (1997; Zbl 0891.68117)]. It requires \(O(n^6m^{1+\delta})\) space and preprocessing time, for any \(\delta >0\) and answers a query in \(O((\sqrt{n}/m^{1/4})\log m)\) time, where \(1\leq m\leq n^2\) (the constants of proportionality depend on \(\delta\)). The author also presents an algorithm that computes, for a given convex polypote \(P\) with \(n\) edges in Euclidean 3-space and a parameter \(0<\varepsilon\leq 1\), two points \(s, t\in \partial P\) such that the geodesic distance between \(s\) and \(t\) is greater or equal than the geodesic diameter of \(P\) multiplied by \(1-\varepsilon\). The running time of the algorithm is \(O(n+1/\varepsilon^5)\). In the contrast, the fastest known algorithm for the exact geodesic diameter takes \(O(n^8\log n)\) time (see the above mentioned paper by \textit{P. K. Agarwal} et al. for more details).
- Computing approximate shortest paths on convex polytopes
- Linear time approximation of 3D convex polytopes
- A tight lower bound for computing the diameter of a 3D convex polytope
- An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
- Approximating geodesic distances on 2-manifolds in image R^3
- Star Unfolding of a Polytope with Applications
- Approximating shortest paths on a convex polytope in three dimensions
- scientific article; zbMATH DE number 910902 (Why is no real title available?)
- Multiple shooting approach for computing approximately shortest paths on convex polytopes
- A near-optimal algorithm for shortest paths among curved obstacles in the plane
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- A survey of geodesic paths on 3D surfaces
- Efficient exact enumeration of single-source geodesics on a non-convex polyhedron
This page was built for publication: Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1283768)
