On the bit complexity of minimum link paths

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the bit complexity of minimum link paths: superquadratic algorithms for problems solvable in linear time

Full text

Pdf (765 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 151 - 158

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Simon Kahan	Tera Computer Company, Seattle, Washington
Jack Snoeyink	UBC Dept. of Comp. Sci., Vancouver, BC, Canada

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): 14, 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/237218.237342 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 , H. Booth , J. O'Rourke , S. Suri, Finding minimal convex nested polygons, Information and Computation, v.83 n.1, p.98-110, Oct. 1989 [doi>10.1016/0890-5401(89)90049-7]
	2	Esther M. Arkin , Joseph S. B. Mitchell , Subhash Suri, Optimal link path queries in a simple polygon, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.269-279, September 1992, Orlando, Florida, United States
	3	B. Chazelle. A theorem on polygon cutting with applications, in Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 339-349, 1982.
	4	H. Davenport. The Higer Arithmetic: An Introduction to the Theory of Numbers. Dover Publications, New York, 1983.
	5	Hristo N. Djidjev , Andrzej Lingas , Jörg-Rüdiger Sack, An O(n log n) algorithm for computing the link center of a simple polygon, Discrete & Computational Geometry, v.8 n.2, p.131-152, 1992 [doi>10.1007/BF02293040]
	6	Subir Kumar Ghosh, Computing the visibility polygon from a convex set and related problems, Journal of Algorithms, v.12 n.1, p.75-95, March 1991 [doi>10.1016/0196-6774(91)90024-S]
	7	Leonidas J. Guibas , David H. Marimont, Rounding arrangements dynamically, Proceedings of the eleventh annual symposium on Computational geometry, p.190-199, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220300]
	8	L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink. Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry ~4 Applications, 3(4):383-415, 1993.
	9	John Hershberger , Jack Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry: Theory and Applications, v.4 n.2, p.63-97, June 1994 [doi>10.1016/0925-7721(94)90010-8]
	10	J. Hobby. Practical segment intersection with finite precision output. Manuscript, 1994.
	11	John D. Hobby, Polygonal approximations that minimize the number of inflections, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.93-102, January 25-27, 1993, Austin, Texas, United States
	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	D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984.
	14	W. Lenhart , R. Pollack, Computing the link center of a simple polygon, Discrete & Computational Geometry, v.3 n.3, p.281-293, Jan., 1988 [doi>10.1007/BF02187913]
	15	V. Milenkovic, Calculating approximate curve arrangements using rounded arithmetic, Proceedings of the fifth annual symposium on Computational geometry, p.197-207, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73856]
	16	V. Milenkovic. Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 500-505, 1989.
	17	Victor Joseph Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, 1988
	18	V. J. Milenkovic. Practical methods for set operations on polygons using exact arithmetic. In Proceedings of the Seventh Canadian Conference on Computational Geometry, pages 55-60, Universit4 Laval, Quebec, 1995.
	19	J. S. B. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica, 8:431-459, 1992.
	20	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	21	Jonathan Sorenson, Two fast GCD algorithms, Journal of Algorithms, v.16 n.1, p.110-144, Jan. 1994 [doi>10.1006/jagm.1994.1006]
	22	Subhash Suri, A linear time algorithm with minimum link paths inside a simple polygon, Computer Vision, Graphics, and Image Processing, v.35 n.1, p.99-110, July 1986 [doi>10.1016/0734-189X(86)90127-1]
	23	Subhash Suri, Minimum link paths in polygons and related problems, 1987

CITED BY 3

	Sariel Har-Peled, An output sensitive algorithm for discrete convex hulls, Proceedings of the fourteenth annual symposium on Computational geometry, p.357-364, June 07-10, 1998, Minneapolis, Minnesota, United States
	Alon Efrat , Sariel Har-Peled, Guarding galleries and terrains, Information Processing Letters, v.100 n.6, p.238-245, 31 December 2006
	Himanshu Gupta , Rephael Wenger, Constructing pairwise disjoint paths with few links, ACM Transactions on Algorithms (TALG), v.3 n.3, p.26-es, August 2007