Plane-sweep algorithms for intersecting geometric figures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Plane-sweep algorithms for intersecting geometric figures

Full text

Pdf (707 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 10 (October 1982) table of contents

Pages: 739 - 747

Year of Publication: 1982

ISSN:0001-0782

Authors

J. Nievergelt	E. T. H, Zurich, Switzerland
F. P. Preparata	Univ. of Illinois, Urbana

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 211, Citation Count: 27

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/358656.358681 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	J.L. Bentley and T,A. Ottmann. Algorithms for reporting and counting geometric intersections. 1EEE Trans. Computers, C-28, 9, (Sept. 1979) 643-647.
	3	J.L. Bentley and D. Wood. An optimal worst case algorithm for reporting intersections of rectangles. 1EEE Trans. Compters. C-29, 7, (July 1980) 571-576.
	4	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	5	E.M. McCreight. Efficient algorithms for enumerating intersecting intervals and rectangles. Report CSL 80-9 XEROX PARC, June 1980.
	6	M.E. Newell and C.M. Sequin. The inside story on selfintersecting polygons. LAMBDA, 1, Second Quarter 1980, 20-24.
	7	M.I. Shamos and D. Hoey. Closest-point problems. 16th IEEE Annual Symposium on Foundations of Computer Science. Berkeley, CA. 1975, 151-162.
	8	M.I. Shamos and D. Hoey. Geometric intersection problems. 17th IEEE Annual Symposium on Foundations of Computer Science. Houston, TX. 1976, 208-215.

CITED BY 27

	A. J. Briggs, An efficient algorithm for one-step planar complaint motion planning with uncertainty, Proceedings of the fifth annual symposium on Computational geometry, p.187-196, June 05-07, 1989, Saarbruchen, West Germany
	Surendra Nahar , Sartaj Sahni, A time and space efficient net extractor, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.411-417, July 1986, Las Vegas, Nevada, United States
	Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984
	Diane Crawford, Technical correspondence, Communications of the ACM, v.36 n.1, p.112-115, Jan. 1993
	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992
	Walter Gish , Allen Tanner, Hardware antialiasing of lines and polygons, Proceedings of the 1992 symposium on Interactive 3D graphics, p.75-86, June 1992, Cambridge, Massachusetts, United States
	Hanan Samet , Robert E. Webber, Storing a collection of polygons using quadtrees, ACM Transactions on Graphics (TOG), v.4 n.3, p.182-222, July 1985
	Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States
	X.-M. Xiong , E. S. Kuh, Nutcracker: an efficient and intelligent channel spacer, Proceedings of the 24th ACM/IEEE conference on Design automation, p.298-304, June 28-July 01, 1987, Miami Beach, Florida, United States
	Martti Mäntylä , Markku Tamminen, Localized set operations for solid modeling, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.279-288, July 1983
	B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987
	P. T. Chapman , K. Clark, Jr., The scan line approach to design rules checking: Computational experiences, Proceedings of the 21st conference on Design automation, p.235-241, June 25-27, 1984, Albuquerque, New Mexico, United States
	L Guibas , R Seidel, Computing convolutions by reciprocal search, Proceedings of the second annual symposium on Computational geometry, p.90-99, June 02-04, 1986, Yorktown Heights, New York, United States
	Kuang-Wei Chiang , Surendra Nahar , Chi-Yuan Lo, Time efficient VLSI artwork analysis algorithms in GOALIE2, Proceedings of the 25th ACM/IEEE conference on Design automation, p.471-475, June 12-15, 1988, Atlantic City, New Jersey, United States
	Mattan Kamon , Steve McCormick , Ken Sheperd, Interconnect parasitic extraction in the digital IC design methodology, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.223-231, November 07-11, 1999, San Jose, California, United States
	Thomas G. Szymanski , Christopher J. Van Wyk, Space efficient algorithms for VLSI artwork analysis, Proceedings of the 20th conference on Design automation, p.734-739, June 27-29, 1983, Miami Beach, Florida, United States
	Xiao-Ming Xiong , Ernest S. Kuh, The constrained via minimization problem for PCB and VLSI design, Proceedings of the 25th ACM/IEEE conference on Design automation, p.573-578, June 12-15, 1988, Atlantic City, New Jersey, United States
	Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
	H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States
	Jyh-Jong Fu , R. C. T. Lee, Minimum Spanning Trees of Moving Points in the Plane, IEEE Transactions on Computers, v.40 n.1, p.113-118, January 1991
	Y.-L. Wang , R. C. Lee , J. S. Chang, The Number of Intersections Between two Rectangular Paths, IEEE Transactions on Computers, v.38 n.11, p.1564-1571, November 1989
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Bernard Chaselle, Intersecting is easier than sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.125-134, December 1984
	Ralf Hartmut Güting , Markus Schneider, Realm-based spatial data types: the ROSE algebra, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.243-286, April 1995
	K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States
	Eynat Rafalin , Diane L. Souvaine, Topological sweep of the complete graph, Discrete Applied Mathematics, v.156 n.17, p.3276-3290, October, 2008
	Jürgen Krämer , Bernhard Seeger, Semantics and implementation of continuous sliding window queries over data streams, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-49, April 2009