An optimal algorithm for intersecting line segments in the plane
Chazelle B, Edelsbrunner H. 1992. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM. 39(1), 1–54.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
Abstract
The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.
Publishing Year
Date Published
1992-01-01
Journal Title
Journal of the ACM
Publisher
ACM
Acknowledgement
B, Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR 87-00917. H, Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the NSF under Grant CCR 87-14565. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for
Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
Volume
39
Issue
1
Page
1 - 54
ISSN
eISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM. 1992;39(1):1-54. doi:10.1145/147508.147511
Chazelle, B., & Edelsbrunner, H. (1992). An optimal algorithm for intersecting line segments in the plane. Journal of the ACM. ACM. https://doi.org/10.1145/147508.147511
Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for Intersecting Line Segments in the Plane.” Journal of the ACM. ACM, 1992. https://doi.org/10.1145/147508.147511.
B. Chazelle and H. Edelsbrunner, “An optimal algorithm for intersecting line segments in the plane,” Journal of the ACM, vol. 39, no. 1. ACM, pp. 1–54, 1992.
Chazelle B, Edelsbrunner H. 1992. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM. 39(1), 1–54.
Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for Intersecting Line Segments in the Plane.” Journal of the ACM, vol. 39, no. 1, ACM, 1992, pp. 1–54, doi:10.1145/147508.147511.
Google Scholar