dynamic space partitioning tree data structures?

Question

I have an application where I need to do nearest neighbor, rectangle/polygon overlap and other basic computational geometry operations against dynamically changing data (all 2d.) I understand the basic data structures in the static case (quadtrees, 2-dimensional Kd-trees, R-trees, BSP, etc.) but I want to understand the state of the art in the dynamic case. The difficulty seems to be knowning when/how to balance on insertion and deletion. For example, is there a dynamic data structure that answers k-nearest neighbors against n points in O(log n + k), where insertion and deletion take O(log n) (amortized, maybe)? Is there a standard reference that summarizes what's known about this problem?

Answer 1

To be honest, I haven't done too much with dynamic trees myself (mostly static). But I believe the Bkd-tree paper (early 2000s?) is good source to start. I believe it has been referenced many times since then. You can use sources like acm/citeseer to track newer papers that reference it. Side note: i think there is public code available for Bkds so you can play with it without investing too much time - see if it works for you.

Bkd-Tree: A Dynamic Scalable kd-Tree Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, and Jeffrey Scott Vitter

Answer 2

You can try a monster curve (space filling curve). A fast algorithm is to simply interleave the x and y coordinate. It also possible for 3 dimensions.