1992/01/02 by Bernard Chazelle, Herbert Edelsbrunner · 3 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #Digital Image Processing Techniques #Intersection (aeronautics) #Plane (geometry) #Algorithm #Line segment #Line (geometry) #Construct (python library) #Time complexity #Subdivision #Computer science #Mathematics #Combinatorics #Discrete mathematics #Geometry
paper · pdf · doi:10.1145/147508.147511
openalex publication_date 1992/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.