An Optimal Algorithm for Intersecting Line Segments in the Plane

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. >

Authors

• Bernard Chazelle
• Herbert Edelsbrunner

Keywords

• Data structures
• Image segmentation
• Processor scheduling
• Computer science
• Computer graphics
• Solid modeling
• Robots
• Costs
• Independent component analysis
• Algorithm design and analysis
• Time Constant
• Entry Point
• Tree Nodes
• Line Segment
• Lower Edge
• Upper Edge
• Binary Search
• Set Of Segments
• Activation Segment
• Exit Point
• Consecutive Events
• Extra Credit
• Augmentation Process
• Persistent Data
• Balanced Tree
• Number Of Credits
• Active Edge
• Left Endpoint
• Segment Endpoints
• Vertical Stripes
• Data Structure
• Red Light
• Space Requirements
• Boundary Region