Shortest path queries in rectilinear worlds of higher dimension (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortest path queries in rectilinear worlds of higher dimension (extended abstract)

Full text

Pdf (890 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 51 - 60

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Mark de Berg	Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, the Netherlands
Marc van Kreveld	Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, the Netherlands
Bengt J. Nilsson	Institute für Informatik, Albert-Ludwigs-Universität Rheinstr., 10-12, D-7800 Freiburg i. Br., Fed. Rep. of Germany

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: 4

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/109648.109654 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	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	2	Canny, J., and J. Reif, New Lower Bound Techniques for Robot Motion Planning Problems. Proc. 29th FOCS (1987), pp. 49-60.
	3	Chazelle, B., A theorem on polygon cutting with applications. Proc. 23rd FOCS (1982), pp. 339-349.
	4	Chazelle, B., Triangulating a Simple Polygon in Linear Time. Proc. 31st FOCS (1990), pp. 220-230.
	5	Chazelle, B., and L.J. Guibas, Fractional Cascading: I. A Data Structuring Technique. Algorithmica 1 (1986), pp. 133-162.
	6	Jindong Chen , Yijie Han, Shortest paths on a polyhedron, Proceedings of the sixth annual symposium on Computational geometry, p.360-369, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98601]
	7	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]
	8	Mark de Berg, On rectilinear link distance, Computational Geometry: Theory and Applications, v.1 n.1, p.13-34, July 1991 [doi>10.1016/S0925-7721(99)00027-9]
	9	M. T. de Berg , M. J. van Kreveld , B. J. Nilsson , M. H. Overmars, Finding shortest paths in the presence of orthogonal obstacles using a combined L1 and link metric, Proceedings of the second Scandinavian workshop on Algorithm theory, p.213-224, July 1990, Bergen, Sweden
	10	de Rezende, P.J., D.T. Lee, and Y.F. Wu, Rectilinear Shortest Paths with Rectangular Barriers. Discr. & Comp. Geom. 4 (1989), pp. 41-53.
	11	Dijkstra, E.W., A Note on Two Problems in Connection with Graphs. Numer. Math. 1 (1959), pp. 269- 271.
	12	Y. Ke, An efficient algorithm for link-distance problems, Proceedings of the fifth annual symposium on Computational geometry, p.69-78, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73841]
	13	Larson, R.C., and V.O. Li, Finding Minimum Rectilinear Distance Paths in the Presence of Barriers. Networks 11 (1981), pp. 285-304.
	14	Der-Tsai Lee, Proximity and reachability in the plane., 1978
	15	Lee, D.T., and F.P. Preparata, Euclidean Shortest Paths in the Presence of Rectilinear Barriers. Networks 14 (1984), pp. 393-410.
	16	W. Lenhart , R. Pollack , J. Sack , R. Seidel , M. Sharir, Computing the link center of a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.1-10, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41959]
	17	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	18	Mitchell, J.S.B., An Optimal Algorithm for Shortest Rectilinear Paths Among Obstacles in the Plane. Abstracts of the 1st Canad. Conf. on Comp. Geom. (1989), p. 22.
	19	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]
	20	Joseph S. B. Mitchell , Günter Rote , Gerhard Woeginger, Minimum-link paths among obstacles in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.63-72, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98537]
	21	J. O'Rourke , C. Schevon, Computing the geodesic diameter of a 3-polytope, Proceedings of the fifth annual symposium on Computational geometry, p.370-379, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73874]
	22	Reif, J., and J.A. Storer, Shortest Paths in Euclidian Space with Polyhedral Obstacles. Techn. Rep. CS- 85-121, Comp. Science Dept., Brandeis University, Waltham, MA, 1985.
	23	Michael Ian Shamos, Computational geometry., 1978
	24	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]
	25	Subhash Suri, Minimum link paths in polygons and related problems, 1987

CITED BY 4

	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
	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
	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
	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