An optimal algorithm for intersecting line segments in the plane
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 4, 590-600
- https://doi.org/10.1109/sfcs.1988.21975
Abstract
The authors present the first optimal algorithm for the following problem: given n line segments in the plane, compute all k pairwise intersections in O(n log n+k) time. Within the same asymptotic cost the algorithm will also compute the adjacencies of the planar subdivision induced by the segments, which is a useful data structure for contour-filling on raster devices.Keywords
This publication has 13 references indexed in Scilit:
- A Functional Approach to Data Structures and Its Use in Multidimensional SearchingSIAM Journal on Computing, 1988
- Applications of random sampling in computational geometry, IIPublished by Association for Computing Machinery (ACM) ,1988
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- Reporting and counting segment intersectionsJournal of Computer and System Sciences, 1986
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Computational GeometryPublished by Springer Nature ,1985
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- Comments on “algorithms for reporting and counting geometric intersections”IEEE Transactions on Computers, 1981
- An Optimal Worst Case Algorithm for Reporting Intersections of RectanglesIEEE Transactions on Computers, 1980
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978