libkdtree vs. BKD-Tree

[Paul Harris]

On 23/04/2008, Willi Richert <richert at c-lab.de> wrote:
>
> Hi,
>
> thanks for the view. Do you then actually use the "logarithmic method" as
> proposed by the BKD authors? I mean, they claim in their paper to
> guarantee
> amortized log time operations (insert, remove, find). As your code looks
> much
> cleaner and shorter to me  I wonder which other method besides BKD you use
> to
> maintain that guarantee. How costly actually is the rebalancing subsequent
> to
> insert/remove?


i didn't read that much in depth actually, so i can't comment on the log
method.  and sorry but its been a while since i've read the code to comment
on the rebalancing costs.  lets see if someone else says something on that.
i forgot to CC the list, i remembered this time.

The next days I will examine how I could wrap it in Python. If someone is
> interested please let me know.


i am not personally interested, but more exposure would also help to
increase the user base and thus the developer base.

one key part of libkdtree is that it is heavy on templates, so i assume
you'd have to specify a fixed set of datatypes and accessors for the python
wrapper?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080423/18fd52ca/attachment.htm