Plane sweep and segment intersections

The event queue is ordered by horizontal position, while a balanced status structure stores active segments from bottom to top immediately to the right of the current event. In an interval with no event, two active segments cannot reverse order without crossing. At an insertion or deletion, only the new neighboring pairs need to be checked. At a proper crossing, the two involved adjacent segments exchange order, and their newly exposed neighbors may create future events.

Why are adjacent pairs sufficient? Just before two segments cross in general position, no third active segment can remain strictly between them at their common point. Otherwise continuity would force another event first or produce the excluded triple intersection. This is a local certificate for the next crossing, not a claim that every pair of intersecting segments is adjacent throughout the sweep. A status comparator must use the intended side of an event consistently; changing a comparison coordinate without repairing the tree can invalidate its ordering.

Orientation signs classify whether finite segments cross, but the queue must also compare the constructed crossing coordinates. For rational input these coordinates are rational and can be compared exactly with suitable arithmetic. Robust input predicates alone do not certify a queue built from uncontrolled rounded intersections. The mathematical running time counts these comparisons at unit cost; exact rational numerator sizes and arithmetic work belong to a separate bit analysis. Output storage also costs at least one operation per reported intersection.

A standard event-queue implementation and stored output may use space proportional to the input plus the number of scheduled or reported events. The logarithmic running-time expression does not mean the sweep uses constant memory or that a dense arrangement is cheap. When the number of crossings is quadratic, explicitly listing them is already quadratic work. An intersection-existence problem can stop after its first certificate and is a different output task from reporting every crossing.

Closed segments can meet at endpoints, several segments can cross at one location, and different event points can have the same horizontal coordinate. A robust broader algorithm groups coincident events, declares a consistent ordering such as lexicographic coordinates, and processes all incident starting, ending, and crossing segments together. Vertical segments require an appropriate local range operation or a sweep convention designed for them. The simple adjacent-pair swap proof above does not, by itself, establish correctness for those cases.

Collinear overlaps are more fundamental: their intersection may be a whole interval containing infinitely many points. A finite crossing-point output is then the wrong specification. One can report overlapping segment pairs with overlap intervals, or split the union into elementary pieces with incidence information. Those choices have different output sizes and event logic. Before extending a sweep implementation, decide whether multiplicity counts points, pairs, or arrangement features; otherwise even the meaning of the claimed output-sensitive bound is unclear.