I just wrote a major expansion of the Wikipedia article on the Bentley–Ottmann algorithm, the plane sweep algorithm for listing all crossings among a set of line segments. As usual, feedback would be very welcome; I already know that it could still use illustrations, and the article on the closely related Shamos–Hoey algorithm for detecting a single crossing is completely missing.

One surprise for me as I was researching this: Chazelle and Edelsbrunner, in their 1992 JACM paper on deterministic \( O(n\log n + k) \) algorithms for constructing arrangements of line segments, leave as an open problem whether it is possible to list all crossings deterministically in the same \( O(n\log n + k) \) time bound as their algorithm but with the \( O(n) \) space bound of Bentley–Ottmann, rather than the larger \( O(n+k) \) required for storing the whole arrangement in memory. I had thought that this was one of the problems solved by topological sweeping, but if so I don't know what the right reference is: the original Edelsbrunner–Guibas topological sweeping paper appears to be only for line arrangements, and the Asano–Guibas–Tokuyama SoCG '91 paper extends the topological sweeping method to the intersection of a line arrangement with a convex region of the plane, but not to arbitrary line segment arrangements. Can this really still be open?

ETA: Seems not to be open; see comments.


  author       = "Ivan J. Balaban",
  title        = "An Optimal Algorithm for Finding Segment
  booktitle    = SOCG_1995,
  year         = 1995,
  pages        = "211--219",
  keywords     = ""

Now, did I ever read this paper? I dont remember...


Thanks, that does at least claim to solve the problem. It looks like it will take some time and effort to understand it, though.

Man, you had 14 years to understand it! How much more time do you want? ;)



Actually, I remember seen balaban as a method in LEDA sometime around 1998 or so. I was surprised that I'd never heard about the algorithm before.

Pat Morin