A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract)

Full text

Pdf (1.45 MB)

Source

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

Nice, France

Pages: 264 - 273

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Christian S. Mata	Department of Computer Science, State University of New York, Stony Brook, NY
Joseph S. B. Mitchell	Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY

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): 9, Downloads (12 Months): 40, Citation Count: 8

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.262983 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	R. Alexander and N. Rowe. Path planning by optimal-pathmap construction for homogeneous-cost two-dimensional regions, in Proc. IEEE Internat. Conf. Robot. Aurora., 1990.
	2	Danny Z. Chen , Kevin S. Klenk , Hung-Yi T. Tu, Shortest path queries among weighted obstacles in the rectilinear plane, Proceedings of the eleventh annual symposium on Computational geometry, p.370-379, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220319]
	3	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]
	4	O. Devillers. Robust and efficient implementation of the Delaunay tree. Report 1619, INRIA Sophia-Antipolis, Valbomae, France, 1992.
	5	D. H. Douglas. Least cost path in geographic information systems. Research note No. 61, Department of Geography, University of Ottawa, Ottawa, Ontario, August 1993.
	6	L. Gewali, A. Meng, J. S. B. Mitchell, and S. Ntafos. Path planning in 0/1/# weighted regions with applications. ORSA J. Comput., 2(3):253-272, Summer 1990.
	7	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	8	P. Johansson. On a weighted distance model for injection moulding. LinkSping Studies in Science and Technology, Thesis No. 604 LiU-TEK-LIC-1997:05, Division of Applied Mathematics, Link3ping University, LinkSping, Sweden, February 1997.
	9	J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
	10	M. Kindl, M. Shing, and N. Rowe. A stochastic approach to the weighted-region problem, I: The design of the path annealing algorithm. Technical report, Computer Science, U.S. Naval Postgraduate School, Monterey, CA, 1991.
	11	M. Kindl, M. Shing, and N. Rowe. A stochastic approach to the weighted-region problem, II: Performance enhancement techniques and experimental results. Technical report, Computer Science, U.S. Naval Postgraduate School, Monterey, CA, 1991.
	12	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.485-486, June 04-06, 1997, Nice, France [doi>10.1145/262839.263101]
	13	M. J. Longtin. Cover and concealment in ModSAF. In Proc. Fourth Conference on Computer Generated Forces and Behavioral Representation, pages 239-247. STRICOM-DMSO, 1994.
	14	M. J. Longtin and D. Megherbi. Concealed routes in ModSAF. In Proc. Fifth Conference on Computer Generated Forces and Behavioral Representation, pages 305-313. STRICOM-DMSO, 1995.
	15	J. S. B. Mitchell. An algorithmic approach to some problems in terrain navigation. In S. Sitharama Iyengar and Alberto Effes, editors, Autonomous Mobile Robots: Perception. Mapping, and Navigation, pages 408-427. IEEE Computer Society Press, Los Alamitos, CA, 1991.
	16	J. S. B. Mitchell. L1 shortest paths among polygonal obstacles in the plane. Algorithmica, 8:55-88, 1992.
	17	Joseph S. B. Mitchell , Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM (JACM), v.38 n.1, p.18-73, Jan. 1991 [doi>10.1145/102782.102784]
	18	J. S. B. Mitchell, D. W. Payton, and D. M. Keirsey. Planning and reasoning for autonomous vehicle control. Internat. J. Iatell. Syst., II:129-198, 1987.
	19	C. H. Papadiraitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Lett., 20:259-263, 1985.
	20	I. Ragnemalm. The Euclidean distance transform. LinkSping Studies in Science and Technology, Ph.D. Dissertation 304, Department of Electrical Engineering, Link#ping University, Sweden, 1993.
	21	R. F. Richbourg, N. C. Rowe, M. J. Zyda, and R. McGhee. Solving global two-dimensional routing problems using Shell's law. In Proc. IEEE Internat. Conf. Robot. Aurora., pages 1631-1636, Raleigh, NC, 1987.
	22	Neil C. Rowe , R. F. Richbourg, An efficient Snell's law method for optimal-path planning across multipole two-dimensional, irregular, homogeneous-cost regions, International Journal of Robotics Research, v.9 n.6, p.48-66, Dec. 1990 [doi>10.1177/027836499000900605]
	23	W. Warntz. Transportation, social physics, and the law of refraction. The Professional Geographer, 9(4):2-7, 1957.
	24	A. C. Yno. On constructing minimum spanning trees in kdimensional spaces and related problems. SIAM J. Comput., 11:721-736, 1982.

CITED BY 8

	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
	Lyudmil Aleksandrov , Anil Maheshwari , Jörg-Rüdiger Sack, Approximation algorithms for geometric shortest path problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.286-295, May 21-23, 2000, Portland, Oregon, United States
	Danny Z. Chen , Ovidiu Daescu , Xiaobo (Sharon) Hu , Xiaodong Wu , Jinhui Xu, Determining an optimal penetration among weighted regions in two and three dimensions, Proceedings of the fifteenth annual symposium on Computational geometry, p.322-331, June 13-16, 1999, Miami Beach, Florida, United States
	Pankaj K. Agarwal , Sariel Har-Peled , Meetesh Karia, Computing approximate shortest paths on convex polytopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.270-279, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Zheng Sun , John H. Reif, On finding approximate optimal paths in weighted regions, Journal of Algorithms, v.58 n.1, p.1-32, January 2006
	Sasanka Roy , Sandip Das , Subhas C. Nandy, Shortest monotone descent path problem in polyhedral terrain, Computational Geometry: Theory and Applications, v.37 n.2, p.115-133, July, 2007
	Ovidiu Daescu , James D. Palmer, Finding optimal weighted bridges with applications, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Yevgeny Schreiber, Shortest paths on realistic polyhedra, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea