W Karas wrote: > After more careful consideration, the only solution > I can see is fairly complex. It is based on using > an AVL-balanced binary search tree.
I think you are being a bit more complex than you need to be. Also, you have a minor error in the details. Your basic idea is: A chord intersects the shortest chord, iff it has an endpoint "inside" the shortest chord. Count those endpoints (endpoints = intersections) and then remove the shortest chord. Repeat, until no chords are left. That is correct. As presented, you were treating the chord from 1 degree to 359 degrees as being a long chord (length = 358 degrees). For your algorithm to work correctly, you need to treat it as a chord of length 2 degrees. So you need "fixup" to correctly handle those chords which "contain" zero degrees. The AVL tree is perhaps more complex than necessary. You can build your tree balanced to begin with (its contents are the integers from 0 to N-1). Each node contains its "descendant" count. When logical deletions occur, don't actually remove any nodes. Just update the "descendant" counts so that they reflect only living descendants. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
