5 ms·
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 da
by stream_fusion 12y ago
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 12y agoOh 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/Quadtree http://en.wikipedia.org/wiki/Z-order_curve http://en.wikipedia.org/wiki/Z-order_curve