Matrix searching with the shortest path metric

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Matrix searching with the shortest path metric

Full text

Pdf (973 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 485 - 494

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

John Hershberger
Subhash Suri

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 22, Citation Count: 3

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/167088.167220 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 , Alok Aggarwal , Boris Aronov , S. Rao Kosaraju , Baruch Schieber , Subhash Suri, Computing external farthest neighbors for a simple polygon, Discrete Applied Mathematics, v.31 n.2, p.97-111, 1991 [doi>10.1016/0166-218X(91)90063-3]
	2	Alok Aggarwal , Herbert Edelsbrunner , Prabhakar Raghavan , Prasoon Tiwari, Optimal time bounds for some proximity problems in the plane, Information Processing Letters, v.42 n.1, p.55-60, April 27, 1992 [doi>10.1016/0020-0190(92)90133-G]
	3	A. Aggarwal, M. Klawe, S. Moran, P. Shot, and R. Wilber. Geometric applications of a matrix searching algorithm. Algorithmica, 2"195-208, 1987.
	4	Alok Aggarwal , Shlomo Moran , Peter W. Shor , Subhash Suri, Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version), Proceedings of the Workshop on Algorithms and Data Structures, p.115-134, August 17-19, 1989
	5	L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
	6	L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
	7	L. Guibas, J. Hershberger, and J. Snoeyink. Compact interval trees: A data structure for convex hulls. International Journal of Computational Geometry Cj Applications, 1(1):1-22, t991.
	8	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	9	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]
	10	J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. In Proceedings of the 2rid Workshop on Algorithms and Data Structures, pages 331-342. Springer- Verlag, 1991. Lecture Notes in Computer Science 519.
	11	Andrzej Lingas, Voronoi diagrams with barriers and the shortest diagonal problem, Information Processing Letters, v.32 n.4, p.191-198, Sept 1, 1989 [doi>10.1016/0020-0190(89)90043-4]
	12	Odile Marcotte , Subhash Suri, Fast matching algorithms for points on a polygon, SIAM Journal on Computing, v.20 n.3, p.405-422, June 1991 [doi>10.1137/0220026]
	13	J. O'Rourke, Computational geometry column 8, ACM SIGACT News, v.20 n.4, p.30-30, Nov. 1989 [doi>10.1145/74074.74081]
	14	M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and Sys~em Sciences, 23:166-204, 1981.
	15	B. Schieber , U. Vishkin, On finding lowest common ancestors: simplification and parallelization (extended summary), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	16	S. Suri, Computing geodesic furthest neighbors in simple polygons, Journal of Computer and System Sciences, v.39 n.2, p.220-235, Oct. 1989 [doi>10.1016/0022-0000(89)90045-7]
	17	Binhai Zhu, Computing the shortest diagonal of a monotone polygon in linear line, Information Processing Letters, v.42 n.6, p.303-307, July 24, 1992 [doi>10.1016/0020-0190(92)90227-M]

CITED BY 3

	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
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Sang Won Bae , Kyung-Yong Chwa, The geodesic farthest-site Voronoi diagram in a polygonal domain with holes, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark