wade wrote: > 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.
The algorithm is based on the recursive reduction: intersections = intersections with chord with min(end - start) + remaining intersections It doesn't matter if the chord with min(end - start) is the shortest chord or not. > 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. I don't see the problem. I think this is based on your misunderstanding that I'm trying to start with the shortest chord. > 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. So you mean sort all the points, then construct a fully balanced tree? I think this might be slower than building an AVL tree insert by insert, but that may be more than canceled out by the faster searches. > When logical > deletions occur, don't actually remove any nodes. Just update the > "descendant" counts so that they reflect only living descendants. This would reduce deletion time, but increase average search time. I would guess you are right that, at least in the average case, it would be an optimization. But it would take some complex analysis to prove this. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---