Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions

Full text

Pdf (1.25 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 359 - 365

Year of Publication: 1997

ISBN:0-89791-878-9

Author

Sariel Har-Peled

School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.263003 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AAOS96	Pankaj K. Agarwal , Boris Aronov , Joseph O'Rourke , Catherine A. Schevon, Star Unfolding of a Polytope with Applications, SIAM Journal on Computing, v.26 n.6, p.1689-1713, Dec. 1997 [doi>10.1137/S0097539793253371]
	AHPSV96	P.K. Agarwal, S. Har-Peled, M. Sha.dr, and K. R. Varadarajan. Approximate shortest paths on a convex polytope in three dimensions. Report CS- 1996-12, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.
	CH96	J. Chen and Y. Han. Shortest paths on a polyhedron; Part I: computing shortest paths. Int. J. Comput. Geom. # Appl., 6(2):127-144, 1996.
	Cla87	K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
	CR87	J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. In Proc. P.8th Annu. IEEE Sympoa. Found. Camput. Sci., pages 49-60, 1987.
	CSY94	Joonsoo Choi , Jürgen Sellen , Chee-Keng Yap, Approximate Euclidean shortest path in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.41-48, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177501]
	DK85	D.P. Dobkin and D. G. Kirkpatrick. A llnear algorithm for determining the separation of convex polyhedra. J. Algorithma, 6:381-392, 1985.
	DK90	David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
	HP97	S. Har-Peled. Constructing approximate shortest path maps in three dimensions, manuscript, 1997.
	HS95	John Hershberger , Subhash Suri, Practical methods for approximating shortest paths on a convex polytope in R3, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.447-456, January 22-24, 1995, San Francisco, California, United States
	MMP87	Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
	Pap85	C. H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Lett., 20:259-263, 1985.
	Pog73	A.V. Pogorelov. Eztrinsic Geometry of Convez Surfaces, Volume 35 of Translations of Mathematical Monographs. American Mathematical Society, Providence, Rhode Island, 1973.
	RS94	John H. Reif , James A. Storer, A single-exponential upper bound for finding shortest paths in three dimensions, Journal of the ACM (JACM), v.41 n.5, p.1013-1019, Sept. 1994 [doi>10.1145/185675.185811]
	Sha87	Micha Sharir, On shortest paths amidst convex polyhedra, SIAM Journal on Computing, v.16 n.3, p.561-572, June 1987 [doi>10.1137/0216038]
	SS86	Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
	VA96	K.R. Varadarajan and P.K. Agarwal. Approximating shortest paths on a polyhedron. manuscript, 1996.

CITED BY 5

	Pankaj K. Agarwal , Sariel Har-Peled , Micha Sharir , Kasturi R. Varadarajan, Approximating shortest paths on a convex polytope in three dimensions, Journal of the ACM (JACM), v.44 n.4, p.567-584, July 1997
	Sariel Har-Peled, Constructing approximate shortest path maps in three dimensions, Proceedings of the fourteenth annual symposium on Computational geometry, p.383-391, June 07-10, 1998, Minneapolis, Minnesota, United States
	Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
	Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.82-91, January 17-19, 1999, Baltimore, Maryland, United States
	Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric spanners, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-34, March 2008