Why would one ever use an Octree over a KD-tree?

Question

I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar data structure for partitioning 3-D Euclidean spaces, but one that works at fixed regular intervals, from what I gather.

A bit of independence research seems to indicate that kd-trees are typically superior in performance for most datasets -- quicker to construct and to query. My question is, what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)? A summary of the advantages and problems of both types would me most appreciated.

As an extra, if anyone could elaborate on the usage of the R-tree data structure and its advantages, I would be grateful for that too. R-trees (more so than octrees) seem to be applied quite similarly to kd-trees for k-nearest-neighbour or range searches.

Answer 1

The cells in a $kD$-tree can have high aspect ratio, whereas octree cells are guaranteed to be cubical. Since this is a theory board, I'll give you the theoretical reason why high aspect ratio is a problem: it makes it impossible to use volume bounds to control the number of cells that you have to examine when solving approximate nearest neighbor queries.

In more detail: if you ask for an $\epsilon$-approximate nearest neighbor to a query point $q$, and the actual nearest neighbor is at distance $d$, you typically end up with a search that examines every data structure cell that reaches from the inside to the outside of an annulus or annular shell with inner radius $d$ and outer radius $(1+\epsilon)d$. If the cells have bounded aspect ratio, as they are in a quadtree, then there can be at most $1/\epsilon^{d-1}$ such cells, and you can prove good bounds on the time for the query. If the aspect ratio is not bounded, as in a $kD$-tree, these bounds do not apply.

$kD$-trees have a different advantage over quadtrees, in that they are guaranteed to have at most logarithmic depth, which also contributes to the time for a nearest neighbor query. But the depth of a quadtree is at most the number of bits of precision of the input which is generally not large, and there are theoretical methods for controlling the depth to be essentially logarithmic (see the skip quadtree data structure).

Answer 2

A group of friends and I are working on a space-RTS game as a fun side project. We're using a lot of the stuff we've learned at Computer Science to make it highly efficient, enabling us to make massive armies later on.

For this purpose we've considered using kd-trees, but we quickly dismissed them: insertions and deletions are extremely common in our program (consider a ship flying through space), and this is an unholy mess with kd-trees. We therefore picked octrees for our game.

Answer 3

what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)?

k-D trees are balanced binary trees and octrees are tries so the advantages and disadvantages are probably inherited from those more general data structures. Specifically:

• Rebalancing can be expensive (octrees don't need rebalancing).
• Balancing handles heterogeneity better because it is adaptive.
• Higher branching factor in octrees means shallower trees (fewer indirections and allocations) for homogeneous distributions.

Also, bisection (as in octrees) lends itself to trivial implementation in terms of bit-twiddling. Similarly, I imagine octrees can benefit greatly from precomputed distances when doing range lookups.

EDIT

Apparently my references to tries and homogeneity need clarification.

Tries are a family of data structures represented by trees of dictionaries and are used as dictionaries for keys that are sequences (most notably strings but also DNA sequences and the bits in a hash value for hash tries). If each dictionary maps one bit of each of x, y and z coordinates (most significant bit in the first level of the trie, next significant bit in the second level etc.) then the trie is an octree that uniformly subdivides 3D space. Hence octrees inherit the characteristics of tries which are, in general:

• High branching factor can mean shallow trees that incur few indirections so searching is fast, e.g. 20 levels of binary tree can be stored in 4 levels of a tree with a branching factor of 256.
• Tries don't get rebalanced during insertions and deletions, saving an expensive operation required for balanced binary trees.

The disadvantage is that heterogeneity can result in imbalanced tries/octrees so searches can require many indirections. The equivalent problem in tries is solved using edge compression to collapse multiple levels of indirection into a single level. Octrees don't do this but there is nothing to stop you from compressing an octree (but I don't think you could call the result an octree!).

For comparison, consider a specialized dictionary for string keys that is represented as a trie. The first level of the trie branches on the first character in the key. The second level on the second character and so on. Any string can be looked up by searching for the first character from the key in the dictionary to obtain a second dictionary that is used to lookup the second character from the key and so on. A set of random key strings would be a homogeneous distribution. A set of key strings that all share some prefix (e.g. all words beginning with "anti") are a heterogeneous distribution. In the latter case, the first dictionary contains only one binding, for "a", the second only one for "n" and so on. Searching for any mapping in the trie always being by searching the same four dictionaries with the same four keys. This is inefficient and this is what octrees do if, for example, they are used to store heterogeneous particle distributions where the vast majority of particles lie in a tiny volume within the vector space.

Answer 4

Octrees are useful as a base datatype for continuum models, see for example the Gerris flow solver. Life is difficult enough in fluid dynamics, so knowing that the sizes of all of your subcubes depends only on their depth must a simplifying factor.

Caveat: I am not a fluid dynamicist!