1988/01/01 by Ketan Mulmuley · 106 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Advanced Image and Video Retrieval Techniques #Partition (number theory) #Intersection (aeronautics) #Algorithm #Partition problem #Simple (philosophy) #Running time #Computer science #Combinatorics #Planar #Set (abstract data type) #Binary logarithm #Mathematics #Randomized algorithm #Discrete mathematics
paper · doi:10.1109/sfcs.1988.21974
openalex publication_date 1988/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A fast randomized algorithm is given for finding a partition of the plane induced by a given set of linear segments. The algorithm is ideally suited for a practical use because it is extremely simple and robust, as well as optimal; its expected running time is O(m+n log n) where n is the number of input segments and m is the number of points of intersection. The storage requirement is O(m+n). Though the algorithm itself is simple, the global evolution of the partition is complex, which makes the analysis of the algorithm theoretically interesting in its own right.>