Try this variation In the previous algorithm if i am correct the complexity is O(n), that itself shows that an important step is missing somewhere. well this is my guess about the algorithm. check if it works. I do not think this is exactly the standard Bentley-Ottmann Algorithm
The precondition would be in going from a point in the circle in a clockwise direction, we must get the start point of a chird first and then only get the corresponding end point. This can be done by swapping the start and enp points appropriately in O(n) 1 ) Radially sort the all the points of each chord (start and end both ). 2 ) Start with the first start point. Insert start point into a Sorted List SL1 Insert corresponding end point into a Sorted List SL2 Have tot=0, done[1..n]=0 3 ) Till all points are done: a ) If its a start point then Insert start point into a Sorted List SL1 Insert corresponding end point into a Sorted List SL2 Find the position of corresponding end point in SL2 say pos tot = tot + pos set done for this point 1 else if it is an end point of a start point processed then Remove the start point from SL1 and end point from SL2 set done for this point 1 4 ) Answer is tot The searching in the sorted list can be done using binary search and therefore the resulting complexity would be O(nlogn) On 4/26/06, pramod <[EMAIL PROTECTED]> wrote: > > I don't think this will work. > Suppose we have two chords which are parallel and both on the one side > of the circle. i.e., say draw a diameter parallel to X and say the > chords are above this parallel to each other. > In that case, your answer will be 1 but they are not intersecting at > all. I think your statement "if you get another start point it means > there is an intersection" is not correct. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---