An optimal algorithm for finding segments intersections

1995/01/01 by Ivan J. Balaban · 2 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Optimization and Packing Problems #Citation #Eleventh #Computer science #Algorithm #Information retrieval #Operations research #Library science #Mathematics #Physics

paper · pdf · doi:10.1145/220279.220302

openalex publication_date 1995/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

This paper deals with a new deterministic algorithm for finding intersecting pairs from a given set of N segments in the plane. The algorithm is asymptotically optimal and has time and space complexity O(AJ log N+ K) and 0( IV ) respectively, where K is the number of intersecting pairs. The algorithm may be used for finding intersections not only line segments but also curve segments.

Citations

• Algorithms for Reporting and Counting Geometric Intersections
• An optimal algorithm for intersecting line segments in the plane
• Applications of random sampling in computational geometry, II
• A fast planar partition algorithm. I
• Optimal Point Location in a Monotone Subdivision
• A data structure for orthogonal range queries

Cited by

• Robust Plane Sweep for Intersecting Segments
• Bentley–Ottmann algorithm [wikipedia]