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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
