In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of ${\displaystyle n}$ line segments with ${\displaystyle k}$ crossings (or intersections), the Bentley–Ottmann algorithm takes time ${\displaystyle {\mathcal {O}}((n+k)\log n)}$. In cases where ${\displaystyle k={\mathcal {o}}\left({\frac {n^{2}}{\log n}}\right)}$, this is an improvement on a naïve algorithm that tests every pair of segments, which takes ${\displaystyle \Theta (n^{2})}$.

The algorithm was initially developed by Jon Bentley and Thomas Ottmann (1979); it is described in more detail in the textbooks Preparata & Shamos (1985), O'Rourke (1998), and de Berg et al. (2000). Although asymptotically faster algorithms are now known by Chazelle & Edelsbrunner (1992) and Balaban (1995), the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements^{[citation needed]}.

The main idea of the Bentley–Ottmann algorithm is to use a sweep line approach, in which a vertical line L moves from left to right (or, e.g., from top to bottom) across the plane, intersecting the input line segments in sequence as it moves. The algorithm is described most easily in its general position, meaning:

In such a case, L will always intersect the input line segments in a set of points whose vertical ordering changes only at a finite set of discrete events. Specifically, a discrete event can either be associated with an endpoint (left or right) of a line-segment or intersection point of two line-segments. Thus, the continuous motion of L can be broken down into a finite sequence of steps, and simulated by an algorithm that runs in a finite amount of time.

There are two types of events that may happen during the course of this simulation. When L sweeps across an endpoint of a line segment s, the intersection of L with s is added to or removed from the vertically ordered set of intersection points. These events are easy to predict, as the endpoints are known already from the input to the algorithm. The remaining events occur when L sweeps across a crossing between (or intersection of) two line segments s and t. These events may also be predicted from the fact that, just prior to the event, the points of intersection of L with s and t are adjacent in the vertical ordering of the intersection points^{[clarification needed]}.

The Bentley–Ottmann algorithm itself maintains data structures representing the current vertical ordering of the intersection points of the sweep line with the input line segments, and a collection of potential future events formed by adjacent pairs of intersection points. It processes each event in turn, updating its data structures to represent the new set of intersection points.

In order to efficiently maintain the intersection points of the sweep line L with the input line segments and the sequence of future events, the Bentley–Ottmann algorithm maintains two data structures:

The algorithm does not need to maintain explicitly a representation of the sweep line L or its position in the plane. Rather, the position of L is represented indirectly: it is the vertical line through the point associated with the most recently processed event.