An O(E\log E + I) Expected Time Algorithm for the Planar Segment Intersection Problem

DOI10.1137/0214046zbMATH Open0568.68056OpenAlexW2087654340MaRDI QIDQ3685220FDOQ3685220

Authors: Eugene W. Myers 

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8405d1e054681b66160d1b06971190575eb63db8

Recommendations

• An optimal algorithm for intersecting line segments in the plane
• Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons
• A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons
• An exponential time parameterized algorithm for planar disjoint paths
• An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points
• Efficient dynamic algorithms for some geometric intersection problems
• Segment intersection searching problems in general settings
• Segment intersection searching problems in general settings
• Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection

zbMATH Keywords

computational geometrydistribution-based searchscan-line algorithmwork list bubble sort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cited In (6)

• A fast planar partition algorithm. I
• A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
• Computational Science and Its Applications – ICCSA 2004
• An algorithm for intersections determination among geometric buffers using skip lists
• Scanline algorithms on a grid
• A tail estimate for Mulmuley's segment intersection algorithm

This page was built for publication: An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685220)