Fast theoretical insertion/removal

[mourner]

I've been thinking about implementing a fast algorithm for insertion and removal, which would allow this spatial index to be used in dynamic use cases. It might get a bit complicated, and it won't be as fast as optimal log(n), but I think it can be made at least log^2(n).

Let's look at a single point insertion. We need to reorder elements in our flat KD array to make it valid after addition of an item, but do this selectively, avoiding sorting the whole array again.

• We have log(n) axis splits that partition the array into KD "nodes".
• When we insert a new point, each split will either stay at its current index (if the number of items was odd), or increase by 1.
• For each split, the new point will belong either to the left half, the right half, or become the new median.
• Let's add the point to the end of the array. Either way, to rearrange the array with respect to the current split, we'll need a constant number of swaps involving the new point, the current median, and a point adjacent to the median (either on the left or on the right).
• For subsequent splits of each half, we perform rearrangement recursively to account for a potential new point (divide & conquer).
• For one axis step, we have to perform the search of point adjacent to the median (because they're not sorted), which is log(n).
• The total complexity of insertion will be O(log(n)) + 2 * O(log(n/2)) + 4 * O(log(n/4)) + ... ~= O(log^2(n).

Does this sound feasible, or are some of my quick assumptions wrong?

cc @anandthakker @mikolalysenko

[slachtar]

Hello, I've a use case, where points are inserted/removed/updated dynamically but not in a hight rate. Could we see an insert/remove functions in the API? Thanks for this great work.

[mourner]

Still not sure if it's possible and pursuing this is too complicated for the benefit, so I'm closing this — better to recommend RBush for cases with insertion/removal.

[kaligrafy]

Is this possible to implement a removal at least, this should be way less complicated than an insertion?

[mourner]

@kaligrafy no, it would be as complicated, and wouldn't make much sense to spent time on given solutions like RBush.