Shortest path queries among weighted obstacles in the rectilinear plane

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortest path queries among weighted obstacles in the rectilinear plane

Full text

Pdf (1.19 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 370 - 379

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Danny Z. Chen	Department of Computer Science and Engineering, University, of Notre Dame, Notre Dame, IN
Kevin S. Klenk	Department of Computer Science and Engineering, University, of Notre Dame, Notre Dame, IN
Hung-Yi T. Tu	Department of Computer Science and Information Management, Providence University, Shalu, Taichung Hsien, 43309, Taiwan, R. O. C.

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): 2, Downloads (12 Months): 33, 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/220279.220319 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	A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix searching algorithm. Algorithmica, 2:209-233, 1987.
	2	Mikhail J. Atallah , Danny Z. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Computational Geometry: Theory and Applications, v.1 n.2, p.79-113, Sept. 1991 [doi>10.1016/0925-7721(91)90002-V]
	3	Mikhail J. Atallah , Danny Z. Chen, On parallel rectilinear obstacle-avoiding paths, Computational Geometry: Theory and Applications, v.3 n.6, p.307-313, Dec. 1993 [doi>10.1016/0925-7721(93)90004-P]
	4	B. ChazeIle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1(2):133- 162, 1986.
	5	Danny Z. Chen, On the all-pairs Euclidean short path problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.292-301, January 22-24, 1995, San Francisco, California, United States
	6	Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.44-53, January 25-27, 1993, Austin, Texas, United States
	7	K. L. Clarkson, S. Kapoor, and P. M. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log3/2 n) time. Submitted for publication.
	8	K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
	9	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 [doi>10.1145/109648.109654]
	10	P. J. de Rezende, D. T. Lee, and Y. F. Wu. Rectilinear shortest paths in the presence of retangular barriers. D~screte ~4 Computational Geometry, 4:41-53, 1989.
	11	H. EIGindy and P. Mitra. Orthogonal shortest route queries among axes parallel rectangular obstacles. International Journal of Computational Geometry and Apphcations, 4(1):3--24, 1994.
	12	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	13	L. Gewali , A. Meng , J. S. Mitchell , S. Ntafos, Path planning in 0/1/ weighted regions with applications, Proceedings of the fourth annual symposium on Computational geometry, p.266-278, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73421]
	14	Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161157]
	15	L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.50-63, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41964]
	16	L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
	17	John Hershberger, A new data structure for shortest path queries in a simple polygon, Information Processing Letters, v.38 n.5, p.231-235, June 14, 1991 [doi>10.1016/0020-0190(91)90064-O]
	18	J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proc. $dth Annual Syrup. on Foundations of Computer Science, pages 508-517, 1993.
	19	M. Iwai, H. Suzuki, and T. Nishizeki. Shortest path algorithm in the plane with rectilinear polygonal obstacles (in Japanese). In Proc. of SIGAL Workshop, Ryukoku University, Japan, July 1994.
	20	K. S. Klenk. Rectilinear shortest path queries among weighted obstacles. Master's thesis, University of Notre Dame, November 1994.
	21	R. C. Larson and V. O. Li. Finding minimum rectilinear distance paths in the presence of barriers. Networks, 11:285-304, 1981.
	22	D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 11:285-304, 1984.
	23	D. T. Lee, C. D. Yang, and T. H. Chert. Shortest rectilinear paths among weighted obstacles. International Journal of Computational Geometry and Applications, 1(2):109-124, 1991.
	24	j. S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Technical Report 832, Cornell University, School of OR/iE, Oct 1988.
	25	J. S. B. Mitchell. An optimal algorithm for shortest rectilinear paths among obstacles. In First Canadian Conference on Computational Geometry, 1989.
	26	J. S. B. Mitchell. L1 shortest paths among polygonal obstacles in the plane. Algorithmica, 8:55-88, 1992.
	27	Joseph S. B. Mitchell, Shortest paths among obstacles in the plane, Proceedings of the ninth annual symposium on Computational geometry, p.308-317, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161156]
	28	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]
	29	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	30	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 [doi>10.1145/185675.185795]
	31	E. Welzl. Constructing the visibility graph for n line segments in O(n2) time. IPL, 20:167-171, 1985.
	32	P. Widmayer. Network design issues in VLSI. Manuscript, 1989. In D. T. Lee, C. D. Yang, and T. H. Chen. Shortest rectilinear paths among weighted obstacles. International journal of Computational Geometry and Applications, 1(2):109-124, 1991.
	33	Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]
	34	C. D. Yang , T. H. Chen , D. T. Lee, Shortest rectilinear paths among weighted rectangles, Journal of Information Processing, v.13 n.4, p.456-462, 1990

CITED BY 2

	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
	Danny Z. Chen , Jinhui Xu, Shortest path queries in planar graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.469-478, May 21-23, 2000, Portland, Oregon, United States