[stream_fusion]

My experience playing around with KD trees is that they are super effective for multidimensional indexing (including spatial) and range search so long as the data is relatively static. The difficulty comes when trying to update and re-balance them dynamically, which is where other structures perform better.

[joe_the_user]

Oh Dear,

I was remembering my previous research wrong.

It's quad-trees and related Z-order based curves that give log(n) search and inserts.

With those, "everything" become log^n.

- Given that, my previous argument concerning log time for triangle/polygon search should stand.

http://en.wikipedia.org/wiki/Quadtree http://en.wikipedia.org/wiki/Z-order_curve