Is there a Tree with deterministic traversal, but which nodes can vary?

Question

I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear.

That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)* in a set of points $P$, the closest point in $S$ where $S\subset P$. The catch its, while $S\subset P$, which elements of $P$ it contains can change at any time.

I was thinking of pre-computing a kd-tree where each leaf contains exactly one element of $P$, and each node/cell has an 'active' property. Then when I get a new $S$ I can recursively 'turn on' the levels of the tree which lead to active leaves. The active branches can then be traversed very quickly, ignoring nodes and leafs which do not contain active points.

The problem with this though is as particles are deactivated the bounding volumne goodness-of-fit will change and its no longer trivial to determine which branch should be traversed when there is a choice.

Is there a tree or spatial subdivision structure that will retain its deterministic traversal property even as points are added and removed (so long as they don't change position)?

The tree should be suitable for traversing on the GPU; primary consideration is performance.

*I've specified $p$ as having three dimensions, but it may have/be able to have 2 or even 1, if it is significant for the tree. Getting into details, $P$ will be an isomap of a 3D triangle mesh, but the mesh will not be simple, therefore its hard to say right now whether the isomap will have less than three dimensions or if the error will be too large if I try to fit it in 1 or 2. Three dimensions will be the worst case.

Answer 1

You can do this with any binary space partitioning tree, such as a k-d tree or an octree.

Your basic approach can actually be made to work. The reason you think it won't work is because you have a misunderstanding about how nearest-neighbor search is done in these trees. Let me show you how they work and how to adapt them to your situation: you'll see that your idea does work fine and is quite a nice approach.

---

The basic principle of nearest-neighbor search is:

• Each subtree represents a (rectangular) region of space.

• You'll keep track of the closest point to $p$ found so far.

• For each subtree T, you'll figure out whether it's possible that any point in the region corresponding to T could be closer to $p$ than the closest found so far. If not (if it's impossible), then you won't look at T or any subtree of T. Otherwise, you'll recursively test each child of T.

This yields a recursive algorithm that explores some subset of the nodes in the tree.

The basic point is that nearest-neighbor search doesn't explore just one path through the tree. Rather, it might "fork" and explore multiple paths. However, it's still faster than looking at every leaf, because they're able to prune some (but not all) subtrees.

---

For example, build an octree representing $P$, the set of all points. Each leaf of the octree corresponds to one point in $P$. Each internal node of the octree corresponds to an "octant" (a rectangular volume of 3D space).

Next, augment the octree as follows: each internal node $x$ has a bit that indicates whether any of the leaves under $x$ are active (whether any of them correspond to points in $S$). Call the octant "active" if it contains at least one point of $S$, so the bit for node $x$ indicates whether the corresponding octant is active. You can update these active bits efficiently: adding or removing a point to $S$ can be done in $O(\log |P|)$ time.

Now, to find the neighbor nearest to point $p$, invoke $\text{Closest}(p, r)$, where $r$ is the root node of the octree and the procedure Closest is defined as follows:

$\text{Closest}(p, x)$:

1. If $x$ is not active, return $\infty$.

2. If $x$ is a leaf, return $d(p,x)$.

3. Otherwise, set $\text{curBest}$ to $\infty$.

4. For each child $y$ of $x$, do:

   • If $y$ is active and $d(p,y) < \text{curBest}$, set $\text{curBest} := \min(\text{curBest}, \text{Closest}(p, y))$.

5. Return $\text{curBest}$.

Here we define $d(p,y)$ (the distance from $p$ to an octant $y$) to be the distance from $p$ to the nearest point in $y$, i.e., the minimum of $d(p,z)$ where $z$ ranges over all points in $y$. Notice that this can be computed efficiently through a straightforward but ugly case analysis.

Notice that the structure of the octree depends only on $P$, but not on which points are active. Thus, you don't need to adjust the partitioning or split points as you change which points are active.

You can do the same with a k-d tree instead of an octree.

There is no guarantee about what the worst-case running time of this procedure will be. However, in practice, I would expect this to be pretty efficient, as large swathes of the octree can be "pruned". In particular, I would expect it to be faster than the naive algorithm of computing $d(p,s)$ for each $s \in S$, if $S$ is large.

Answer 2

You could use a tree that uses a space filling curve, such as the PH-Tree (z-ordered) or a critbit tree (for example z-ordered or hilbert-ordered). The space filling curve ensures that:

• the order of the entries never changes, unless the entries change their geometric position. In other words, the order of traversal depends only on geometric properties of the entries, not on the order of insertion (or deletion); insertion or deletion will not affect the ordering; if a deleted point is reinserted, it will be inserted in the same location as it was before. In your terms, the ordering can be called deterministic.
• entries that are close in space tend to be close in the linear ordering

Hilbert ordering has a better mapping of spatial proximity to proximity in the linear ordering, but it is slower and much more complicated.

Critbit (Java) is quite simple compared to a PH-Tree (Java), but it is much slower for range queries or kNN-queries. The PH-Tree is essentially a quadtree where the ordering inside every node follows the z-ordering of the node's entries and sub-nodes. The critbit tree is a binary tree (prefix sharing trie), that stores entry ordered by their z-value.