Given a set S of disjoint 2D line segments, is there a way to pre-process S into a data structure that can check if a single arbitrary segment L intersects any segment in S in log2(n) time, as well as modify the structure using the same time complexity bounds?The endpoints in S are closed, and lines may have slopes.Sweep-lines result in worst case performance of n log n if every segment needs to be added to the line before checking, and spatial indices like interval trees won't work if multiple segments have overlapping coordinate intervals in every dimension and still doesn't intersect. Algorithms like Shamos Hoey only processes entire sets of segments.Is this simply a specific case of red-blue intersection with one set having size 1, or can the limited scope of the query be used to achieve better performance compared to the general algorithms?
Possible to find intersections between a line segment and a disjoint set in log2(n)?
algorithms;data structures;performance