Constructing approximate shortest path maps in three dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing approximate shortest path maps in three dimensions

Full text

Pdf (1.25 MB)

Source

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

Minneapolis, Minnesota, United States

Pages: 383 - 391

Year of Publication: 1998

ISBN:0-89791-973-4

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): 6, Downloads (12 Months): 27, Citation Count: 2

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/276884.276927 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.

	1	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 [doi>10.1145/263867.263869]
	2	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	3	GAUntlY, J,j AND RBW, J. H. New lower bound techrdques for robot motion planning problems. In Proc. 98th Annu. IEBE Sympon. Found. Comput. Sci. (1987), pp, 49--60.
	4	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	5	CIxgt#, J., AND HAN, Y. Shortes# paths on a polyhedron; Par# h computing shorLest paths. Int. J. Comput Gcom, # Appl. 6, 2 (1996), 127-144.
	6	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]
	7	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]
	8	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	9	DoBKn#, D. P., AND KHtKPATRIOK, D. G. A linear algorlthm for determining the separation of convex polyhedra. Y. Algorithme 6 (1985), 381-392.
	10	FOItTUt;B, S. J. A sweepline algorithm for Voronoi diagrams. Algorithmlea 2 (1987), 153-174.
	11	Sariel Har-Peled, Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.359-365, June 04-06, 1997, Nice, France [doi>10.1145/262839.263003]
	12	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
	13	Mark Lanthier , Anil Maheshwari , Jörg-Rüdiger Sack, Approximating weighted shortest paths on polyhedral surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.274-283, June 04-06, 1997, Nice, France [doi>10.1145/262839.262984]
	14	Christian S. Mata , Joseph S. B. Mitchell, A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract), Proceedings of the thirteenth annual symposium on Computational geometry, p.264-273, June 04-06, 1997, Nice, France [doi>10.1145/262839.262983]
	15	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Journal of Computer and System Sciences, v.50 n.2, p.203-208, April 1995
	16	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]
	17	MOUNT, D. M. Storing the subdividon of a polyhedral surface. Discrete Comput. Geom. 9 (1987), 153-174.
	18	Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
	19	P####ou, C. H. An algorithm for shortest-path motion in three dimensions, inform. Pracess. Zett. #0 (19s0, 259-263.
	20	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]
	21	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]
	22	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]
	23	Xue-Hou Tan , Tomio Hirata , Yasuyoshi Inagaki, Spatial point location and its applications, Proceedings of the international symposium on Algorithms, p.241-250, August 1990, Tokyo, Japan
	24	Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximating Shortest Paths on a Nonconvex Polyhedron, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.182, October 19-22, 1997

CITED BY 2

	Pankaj K. Agarwal , Boris Aronov , Sariel Har-Peled , Micha Sharir, Approximation and exact algorithms for minimum-width annuli and shells, Proceedings of the fifteenth annual symposium on Computational geometry, p.380-389, June 13-16, 1999, Miami Beach, Florida, United States
	Joseph S. B. Mitchell , Micha Sharir, New results on shortest paths in three dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA