Abstract
We consider the problem of computing all intersections between two sets S and T of line segments in the plane, where no two segments in S (similarly, T) intersect. We present an asymptotically optimal algorithm which reports all those intersections in O(n log n + k) time and O(n) space, where n is the total number of line segments, and k is the number of intersections. Our algorithm works also for general arcs of single-valued curves, within the same time bounds. Applications include the intersection of two polygons and the “merge” of two planar maps in time O(n log n + m) and space O(n + m), where n and m are the number of input and output edges, respectively. In the case of straight line segments, a simple modification allows us to count the number of intersections (without reporting them) in time O((n +√ nk)log n) = O(n 1.5log n).
The work of this author was partially supported by Xerox PARC, the University of São Paulo, and the Brazilian Science and Technology Development Council (CNPq).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman: The design and analysis of computer algorithms. Addison-Wesley, Reading (1974).
B. G. Baumgart: A polyhedron representation for computer vision. Proc. of the AFIPS National Computer Conference vol. 44 (1975), 589–596.
J. L. Bentley and Th. A. Ottman: Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, vol. C-28 no. 9 (Sept. 1979), 643–647.
J. L. Bentley and D. Wood: An optimal worst-case algorithm for reporting intersections of rectangles. IEEE Transactions on Computers, vol. C-29 no. 7 (July 1980), 571–577.
B. Chazelle: Reporting and counting arbitrary planar intersections. Technical Report CS-83-16, Department of Computer Science, Brown University (June 1983). Submitted to the Journal of Algorithms.
D. P. Dobkin: Personal communication.
D. Greene and F. Frances Yao: Finite-resolution computational geometry. Manuscript (1986).
L. J. Guibas and J. B. Saxe: Problem 80-15: Computing the connected components of a collection of rectangles. Journal of algorithms vol. 1 (1980), 212, and vol. 4 (1983), 177–181.
L. J. Guibas and R. Seidel: Computing convolutions by reciprocal search. Proc. 2nd ACM Symp. on Computational Geometry (1986), 90–99.
L. J. Guibas and M. Sharir: Computing the unbounded component of an arrangement of line segments. Manuscript (Jan. 1987).
L. J. Guibas and J. Stolfi: Notes on computational geometry. CS445 lecture notes, CS Department, Stanford University (Winter 1982).
D. E. Knuth: The Art of Computer Programming, vol I: Fundamental Algorithms (2nd edition). Addison-Wesley (1973).
H. G. Mairson: Reporting line segment intersections. Manuscript (1981).
E. M. McCreight: Efficient algorithms for enumerating intersecting intervals and, rectangles. Report CSL 80–9, Xerox Palo Alto Research Center (June 1980).
S. Mowchenko: Ph. D. Thesis. Department of Electrical Engineering, University of Waterloo, Ontario, Canada.
D. E. Muller and F. P. Preparata: Finding the intersection of two convex poly-hedra. Theoretical Computer Science vol. 7 (1978), 217–236.
J. Nievergelt and F. P. Preparata: Plane-sweep algorithms for intersecting geo metric figures. Communications of the ACM vol. 25 no. 10 (Oct. 1982), 739–747.
E. M. Reingold: On the optimality of some set algorithms. Journal of the ACM vol. 19 no. 4 (Oct. 1972), 649–659.
M. I. Shamos and D. Hoey: Geometric intersection problems. Proc. of the 17th IEEE Symp. on Foundations of Computer Science (1976), 208–215.
D. D. Sleator and R. E. Tarjan: Self-adjusting binary trees. Proc. of the 15th ACM Symp. on Theory of Computing (1983), 235–245.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mairson, H.G., Stolfi, J. (1988). Reporting and Counting Intersections Between Two Sets of Line Segments. In: Earnshaw, R.A. (eds) Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series, vol 40. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-83539-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-83539-1_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-83541-4
Online ISBN: 978-3-642-83539-1
eBook Packages: Springer Book Archive