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(start - end) +
remaining intersections
It doesn't matter if the chord with min(start - end) 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
-~----------~----~----~----~------~----~------~--~---
