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.





Comments:

None:
2009-05-27T16:43:35Z
@inproceedings{b-oafsi-95,
  author       = "Ivan J. Balaban",
  title        = "An Optimal Algorithm for Finding Segment
                  Intersections",
  booktitle    = SOCG_1995,
  year         = 1995,
  pages        = "211--219",
  keywords     = ""
}

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

--Sariel

11011110:
2009-05-27T16:55:57Z
Thanks, that does at least claim to solve the problem. It looks like it will take some time and effort to understand it, though.
None:
2009-05-27T16:59:19Z

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

--S

None:
2009-05-30T12:49:16Z

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