Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time

Full text

Pdf (658 KB)

Source

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

Waterloo, Ontario, Canada

Pages: 251 - 257

Year of Publication: 1987

ISBN:0-89791-231-4

Authors

K. Clarkson	AT&T Bell Laboratories, Murray Hill, New Jersey
S. Kapoor	AT&T Bell Laboratories, Murray Hill, New Jersey
P. Vaidya	AT&T Bell Laboratories, Murray Hill, New Jersey

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): 5, Downloads (12 Months): 23, Citation Count: 19

Additional Information:

abstract 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/41958.41985 What is a DOI?

ABSTRACT

The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear (L1) path from a point s to a point t which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an &Ogr;(n (logn)2) algorithm for finding such a path, where n is the number of vertices of the obstacles. We also study the case of rectilinear obstacles in three dimensions, and show that L1 shortest paths can be found in &Ogr;(n2(log n)3) time.

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.

	D	E. W. Dijkstra, A note on two problems in connexion with graphs. Numer. Math., I (1959) pp. 269- 271.
	GS	L. Guibas and J. Stolfi. On computing a; north-east nearest neighbors in the f., metric. Unpublished manuscript.
	LL	R. C. Larson and V. 0. Li. Finding minimum rectilinear paths in presence of barriers, Networks, I I, 1981, 285-303.
	LP	D. T. Lee and F. P. Prcparata, Euclidean shortest paths among rectilinear barriers. Networks, 14. 19114, pp. 393-d IO.
	LPW	Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
	RPW	P. J. de Rezende, D. T. Lee, and Y. F. Wu. Rectilinear shortest paths with rectangular barriers. Proc. 2nd Annual Conf. Computational Geometry. pp. 205213.

CITED BY 19

	Narendra V. Shenoy , William Nicholls, An efficient routing database, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Thorsten Adler , Erich Barke, Single step current driven routing of multiterminal signal nets for analog applications, Proceedings of the conference on Design, automation and test in Europe, p.446-450, March 27-30, 2000, Paris, France
	A. Hetzel, A sequential detailed router for huge grid graphs, Proceedings of the conference on Design, automation and test in Europe, p.332-339, February 23-26, 1998, Le Palais des Congrés de Paris, France
	M. Atallah , D. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.270-279, July 02-06, 1990, Island of Crete, Greece
	Masao Sato , Kazuto Kubota , Tatsuo Ohtsuki, A hardware implementation of gridless routing based on content addressable memory, Proceedings of the 27th ACM/IEEE conference on Design automation, p.646-649, June 24-27, 1990, Orlando, Florida, United States
	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
	Yong K. Hwang , Narendra Ahuja, Gross motion planning—a survey, ACM Computing Surveys (CSUR), v.24 n.3, p.219-291, Sept. 1992
	James A. Storer , John H. Reif, Shortest paths in the plane with polygonal obstacles, Journal of the ACM (JACM), v.41 n.5, p.982-1012, Sept. 1994
	J. S. Mitchell, On maximum flows in polyhedral domains, Proceedings of the fourth annual symposium on Computational geometry, p.341-351, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Mark de Berg , Marc van Kreveld , Bengt J. Nilsson, Shortest path queries in rectilinear worlds of higher dimension (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.51-60, June 10-12, 1991, North Conway, New Hampshire, United States
	Boaz Ben-Moshe , Matthew J. Katz , Joseph S. B. Mitchell, Farthest neighbors and center points in the presence of rectngular obstacles, Proceedings of the seventeenth annual symposium on Computational geometry, p.164-171, June 2001, Medford, Massachusetts, 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
	Jin-Yih Li , Yih-Lang Li, An efficient tile-based ECO router with routing graph reduction and enhanced global routing flow, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Moshe Dror , Alon Efrat , Anna Lubiw , Joseph S. B. Mitchell, Touring a sequence of polygons, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Joonsoo Choi , Chee-Keng Yap, Rectilinear geodesics in 3-space (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.380-389, June 05-07, 1995, Vancouver, British Columbia, Canada
	Chung-Wei Lin , Szu-Yu Chen , Chi-Feng Li , Yao-Wen Chang , Chia-Lin Yang, Efficient obstacle-avoiding rectilinear steiner tree construction, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Avijit Sarkar , Rajan Batta , Rakesh Nagi, Finding rectilinear least cost paths in the presence of convex polygonal congested regions, Computers and Operations Research, v.36 n.3, p.737-754, March, 2009
	Liang Li , Evangeline F. Y. Young, Obstacle-avoiding rectilinear Steiner tree construction, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Rajasekhar Inkulu , Sanjiv Kapoor, Planar rectilinear shortest path computation using corridors, Computational Geometry: Theory and Applications, v.42 n.9, p.873-884, November, 2009