Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions (Q1283768)

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).