[Glug-nith-discuss] a problem for anyone to solve...

[Satyajit Sarangi]

Hi guys....
          I am working on a problem these days and thought it would be rather good to throw it out to anyone who can come up with a good solution.. 

Problem Definition: Given n Polylines on a plane. Find all intersections among them. 

Polyline Definition (in case you don't know): A Polyline is a curve basically made up of a lot of straight lines.. so you can imagine it to be a curve made by joining a couple of small straight lines.

Initial place to start: This is a problem from the field of computational geometry.. can be found in ur algo's book (Cormen). 
                              Most places on net will describe this problem for the sweep line algorithm. 

O(n^2) algorithm is to just to do a brute force algorithm. 

O(nlogn) algo - sweep line algo.. 

Problem with sweep line algorithm - has to handle a lot of degeneracies. Also the basic problem definition for sweep line algo is for multiple line segments which may or may not be connected. 

I have my own implementation of this using a Bounding box tree which is simply a binary search tree. 

Want to see if you brilliant guys have some more ideas of how this could be implemented...

Thanks..
Satyajit