Journal of the ACM Bibliography
Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, and Kasturi R. Varadarajan.
Approximating shortest paths on a convex polytope in three dimensions.
Journal of the ACM, 44(4):567-584, July 1997.
[BibTeX entry]
Categories and Subject Descriptors:
F.2.2 [Analysis of Algorithms and Problem Complexity]:
Nonnumerical Algorithms and Problems -- geometrical problems and
computations
General Terms:
Algorithms, Theory
Additional Key Words and Phrases:
Approximation algorithms, convex polytopes, Euclidean shortest paths
Selected papers that cite this one
Selected references
- Avikam Baltsan and Micha Sharir. On the shortest paths between two
convex polyhedra. Journal of the ACM, 35(2):267-287,
April 1988.
- John Canny and John Reif. New lower bound techniques
for robot motion planning problems. In 28th Annual Symposium
on Foundations of Computer Science, pages 49-60, Los Angeles,
California, 12-14 October 1987. IEEE.
- Kenneth L. Clarkson. Approximation algorithms
for shortest path motion planning (extended abstract). In
Proceedings of the Nineteenth Annual ACM Symposium on Theory of
Computing, pages 56-65, New York City, 25-27 May 1987.
- David P. Dobkin and David G. Kirkpatrick. A linear algorithm for
determining the separation of convex polyhedra. Journal of
Algorithms, 6(3):381-392, September 1985.
- David P. Dobkin and David G. Kirkpatrick. Determining
the separation of preprocessed polyhedra -- a unified approach. In
Michael S. Paterson, editor, Automata, Languages and Programming,
17th International Colloquium, volume 443 of Lecture Notes
in Computer Science, pages 400-413, Warwick University, England,
16-20 July 1990. Springer-Verlag.
- John Hershberger and Subhash Suri. Practical methods for
approximating shortest paths on a convex polytope in R^3.
In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 447-456, San Francisco, California, 22-24
January 1995.
- Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The
discrete geodesic problem. SIAM Journal on Computing,
16(4):647-668, August 1987.
- Christos H. Papadimitriou. An algorithm for
shortest-path motion in three dimensions. Information
Processing Letters, 20(5):259-263, 12 June 1985.
- John H. Reif and James A. Storer. A single-exponential upper bounds
for finding shortest paths in three dimensions. Journal of the
ACM, 41(5):1013-1019, September 1994.
- Micha Sharir. On shortest paths
amidst convex polyhedra. SIAM Journal on Computing,
16(3):561-572, June 1987.
- Micha Sharir and Amir Schorr. On shortest paths
in polyhedral spaces. SIAM Journal on Computing,
15(1):193-215, February 1986.
- Kasturi R. Varadarajan and Pankaj K. Agarwal. Approximating shortest
paths on a nonconvex polyhedron. In 38th Annual Symposium on
Foundations of Computer Science, pages 182-191, Miami Beach,
Florida, 20-22 October 1997. IEEE.
Shortcuts: