Topological Bentley–Ottman?
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:
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
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.
2009-05-27T16:59:19Z
Man, you had 14 years to understand it! How much more time do you want? ;)
--S
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