LIPIcs.ISAAC.2016.60.pdf
- Filesize: 0.54 MB
- 13 pages
Document
Approximate Shortest Distances Among Smooth Obstacles in 3D
Authors
-
Part of:
Volume:
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-12-07
Cite AsGet BibTex
Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.60
https://doi.org/10.4230/LIPIcs.ISAAC.2016.60
Abstract
We consider the classic all-pairs-shortest-paths (APSP) problem in a three-dimensional environment where paths have to avoid a set of smooth obstacles whose surfaces are represented by discrete point sets with n sample points in total. We show that if the point sets represent epsilon-samples of the underlying surfaces, (1 ± O(sqrt{epsilon}))-approximations of the distances between all pairs of sample points can be computed in O(n^{5/2} log^2 n) time.
Keywords
- Geodesic distances; approximation algorithm; epsilon sample
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads