The Bentley-Ottmann algorithm processes a sequence of 2n + k events, where n denotes the number of input line segments and k denotes the number of crossings.
described a highly space-efficient version of the Bentley-Ottman algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only O(log2n) additional memory cells.