32
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I should note that both kd-trees and R-trees (but not octrees) seem specifically designed to facilitate k-nearest neighbour searches -- how do they compare in this sense? $\endgroup$ – Noldorin Oct 5 '11 at 1:44
  • $\begingroup$ One note is that kd-trees have guaranteed small depth. Compressed quad trees can get you there, but are less convenient. $\endgroup$ – Suresh Venkat Oct 5 '11 at 6:34
  • $\begingroup$ @Suresh Venkat: Thanks for that. I'm not familiar with compressed quadtrees, but would they really be suitable for 3-D spatial reps? Perhaps there is a "compressed octree" analogue. $\endgroup$ – Noldorin Oct 5 '11 at 14:55
  • $\begingroup$ I have also heard that octrees are more appropriate when one has a known Z-order (space-filling) curve, but am not quite sure on the reasoning here. $\endgroup$ – Noldorin Oct 5 '11 at 14:57
23
$\begingroup$

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).

$\endgroup$
  • 4
    $\begingroup$ See Sariel Har-Peled's recent textbook for a modern summary of compressed quadtrees. $\endgroup$ – Jeffε Jun 12 '12 at 20:16
  • $\begingroup$ Thanks for a good quantitative summary, David. Just to confirm: is your use of "aspect ratio" synonymous with "branching ratio"? I'll definitely have to check into skip quadrees/octrees and also compressed quadtrees/octrees perhaps. $\endgroup$ – Noldorin Jun 12 '12 at 21:52
  • 1
    $\begingroup$ The aspect ratio of a rectangular box can be defined as the ratio of its longest edge length to its shortest edge length. I don't know what branching ratio is supposed to mean in this context but aspect ratio is unrelated to the branching factor of the trees (which is constant for both data structures). $\endgroup$ – David Eppstein Jun 13 '12 at 3:00
  • $\begingroup$ I missed the "cells in". Makes sense now. $\endgroup$ – Noldorin Jun 13 '12 at 15:11
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ah yes, I've heard this before too. Insertion/deletion with kd-trees is a costly operation (due to re-balancing). I believe the best-case time complexities are still the same however... $\endgroup$ – Noldorin Oct 5 '11 at 14:59
  • 2
    $\begingroup$ It depends how you go about fixing the kd-tree. A good best-case time complexity is not something I generally aim for: for example bogosort has an O(1) best-case complexity, but I hope no one uses it. $\endgroup$ – Alex ten Brink Oct 5 '11 at 15:38
  • $\begingroup$ Unfortunately I can't seem to find any good summaries of time complexities for common operations on these data structures, but not to mind. Average-case time complexity is often insightful... $\endgroup$ – Noldorin Oct 5 '11 at 20:50
  • 1
    $\begingroup$ I really think you'd still do better if you just used a KD-tree that cycled axes and simply divided the space down the middle. Skip the bulky SAH and other expensive median cuts and you'll end up with something that not only searches faster than an octree but also builds faster. Since you're partitioning the space evenly as you would with an octree, but with a binary tree rather than an 8-ary tree, whatever you were doing before for removals shouldn't be any more complex with the KD-tree, as it'll be evenly-spaced in a similar way. Ex: you might simply remove empty nodes beyond a depth of N. $\endgroup$ – Dragon Energy May 8 '15 at 10:35
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "octrees are tries"? Also, what do you mean by "handles heterogeneity better"? Homogeneous isn't a word I've encountered with respect to trees. $\endgroup$ – Noldorin Jun 12 '12 at 14:26
  • 2
    $\begingroup$ "Octtrees don't need rebalancing"? That's absolutely not true for octtrees that store heterogeneous point distributions. Alternately, depending on how generally you define "octtree": Rebalancing an octtree is simply impossible, no matter how desirable it might be. $\endgroup$ – Jeffε Jun 12 '12 at 20:15
  • $\begingroup$ @Noldorin "octrees are tries". Yes. Do you know what a trie is? en.wikipedia.org/wiki/Trie $\endgroup$ – Jon Harrop Jun 13 '12 at 9:22
  • $\begingroup$ @Noldorin "Homogeneous isn't a word I've encountered with respect to trees". I'm referring to the homogeneity of the distribution that is being partitioned. For example, when partitioning particles in a 3D space then atoms in a solid are homogeneously distributed whereas stars in the universe are heterogeneously distributed. k-D trees are more likely to be preferable for heterogeneous distributions because their subdivision of space is adaptive. $\endgroup$ – Jon Harrop Jun 13 '12 at 9:26
  • $\begingroup$ @JɛffE "Rebalancing an octtree is simply impossible". That's exactly what I was referring to. Apologies if my wording was confusing. $\endgroup$ – Jon Harrop Jun 13 '12 at 9:27
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Interesting. I can definitely appreciate that octrees are simpler to work with in continuum models... I wonder what the reason is for graphics programming though? $\endgroup$ – Noldorin Oct 5 '11 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.