After more careful consideration, the only solution I can see is fairly complex. It is based on using an AVL-balanced binary search tree. In each node of the AVL tree, a count is kept of the total number of nodes in the subtree that the node is the root of. I think it is the case that the following are all O(log n) operations on this data structure: search, insert, delete, and finding the number of nodes whose key is less/greater than a given key.
A point on a circle can be uniquely identified by the angle of the radius line running to the point. For each chord, let the endpoint with the smaller angle be called the starting point, and let the endpoint with the larger angle be called the ending point. (Note that this algorithm assumes that no two chords have a common endpoint.) 1. Into an AVL tree T, insert the angles of the endpoints of all the chords. In the AVL tree, the size of each subtree is stored in its root node, as described above. 2. Sort the chords ascendingly by the difference given by subtracting the angle of the starting point from the angle of the ending point. (If two chords have the same difference between start and end, the relative ordering is arbibrary.) 3. Set tot = 0 4.1. Iterate over the chords in the order that resulted from step 2. 4.2. Use T to determine Pe -- the number of endpoints less than the ending point of the current cord. 4.3. Use T to determine Ps -- the number of endpoints less than the starting point of the current cord. 4.4. Let tot = tot + Pe - Ps - 1, which adds the number of endpoints between the start and end of the chord to tot. 4.5. Delete the starting point of the current chord from T. Delete the ending point of the current chord from T. These deletions insure that, for succeeding chords in the iteration, each starting and ending point seen that is between the start and end of the chord correspond to a unique intersecting chord. That is because, if one of these starting points were connected to one of the ending points, its endpoints would have already been eliminated in a preceeding iteration. It is also thus insured that each intersection is counted only one time. 4.6. End of iteration over chords. The last chord can be skipped because any intersections it has will already have been counted. 'tot' now contains the number of intersections. All the substeps of step 4 are either O(log n) or O(1), so step 4 is O(n * log n). All of the other steps are O(n * log n) or O(1), so the overall algorithm is O(n * log n). --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
