<p>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.</p>

<p>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.</p>

<p>$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).</p>

CC BY-SA 3.0
2012-06-12T20:16:00.270Z
See Sariel Har-Peled's recent textbook for a modern summary of compressed quadtrees.
Jeffε
CC BY-SA 3.0
2012-06-12T21:52:21.590Z
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.
Noldorin
CC BY-SA 3.0
2012-06-13T03:00:15.137Z
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).
David Eppstein
CC BY-SA 3.0
2012-06-13T15:11:25.437Z
I missed the "cells in". Makes sense now.
Noldorin
CC BY-SA 3.0
2012-06-12T20:12:26.833Z
2012-06-12T20:12:26.833Z
David Eppstein
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-05T14:59:12.003Z
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...
Noldorin
CC BY-SA 3.0
2011-10-05T15:38:09.330Z
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.
Alex ten Brink
CC BY-SA 3.0
2011-10-05T20:50:06.370Z
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...
Noldorin
CC BY-SA 3.0
2015-05-08T10:35:50.200Z
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.
DataMatters
CC BY-SA 3.0
2011-10-05T09:14:49.760Z
2011-10-05T09:14:49.760Z
Alex ten Brink
<blockquote>
  <p>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)?</p>
</blockquote>

<p>k-D trees are balanced binary trees and octrees are <a href="http://en.wikipedia.org/wiki/Trie">tries</a> so the advantages and disadvantages are probably inherited from those more general data structures. Specifically:</p>

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

<p>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.</p>

<p><strong>EDIT</strong></p>

<p>Apparently my references to tries and homogeneity need clarification.</p>

<p><a href="http://en.wikipedia.org/wiki/Trie">Tries</a> 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:</p>

<ul>
<li>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.</li>
<li>Tries don't get rebalanced during insertions and deletions, saving an expensive operation required for balanced binary trees.</li>
</ul>

<p>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!).</p>

<p>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 <em>homogeneous</em> distribution. A set of key strings that all share some prefix (e.g. all words beginning with "anti") are a <em>heterogeneous</em> 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.</p>

CC BY-SA 3.0
2012-06-12T14:26:01.610Z
"octrees are tries"? Also, what do you mean by "handles heterogeneity better"? Homogeneous isn't a word I've encountered with respect to trees.
Noldorin
CC BY-SA 3.0
2012-06-12T20:15:03.440Z
"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.
Jeffε
CC BY-SA 3.0
2012-06-13T09:22:59.200Z
@Noldorin "octrees are tries". Yes. Do you know what a trie is? http://en.wikipedia.org/wiki/Trie
J D
CC BY-SA 3.0
2012-06-13T09:26:55.280Z
@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.
J D
CC BY-SA 3.0
2012-06-13T09:27:40.367Z
@JɛﬀE "Rebalancing an octtree is simply impossible". That's exactly what I was referring to. Apologies if my wording was confusing.
J D
CC BY-SA 3.0
2012-06-13T15:07:50.837Z
@JonHarrop: Ah right; that makes perfect sense now, ta.
Noldorin
CC BY-SA 3.0
2012-06-13T15:15:03.930Z
_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!)._ — No, you call it a compressed octtree.  Again, see Har-Peled's book for an up-to-date discussion.
Jeffε
CC BY-SA 3.0
2012-06-13T17:43:38.880Z
@JɛﬀE The contents of that book doesn't list anything on octrees and only one chapter on quadtrees and it doesn't mention compression in its title. How many pages are devoted to compressed quadtrees?
J D
CC BY-SA 3.0
2012-06-12T10:09:05.283Z
2012-06-13T10:38:26.447Z
2012-06-13T10:38:26.447Z
J D
<p>Octrees are useful as a base datatype for continuum models, see for example the <a href="http://gfs.sourceforge.net/wiki/index.php/Main_Page" rel="nofollow">Gerris</a> 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.</p>

<p>Caveat: I am not a fluid dynamicist!  </p>

CC BY-SA 3.0
2011-10-05T14:52:34.077Z
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?
Noldorin
CC BY-SA 3.0
2011-10-05T08:44:59.463Z
2011-10-05T08:44:59.463Z
jjg
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-05T01:44:19.917Z
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?
Noldorin
CC BY-SA 3.0
2011-10-05T06:34:13.183Z
One note is that kd-trees have guaranteed small depth. Compressed quad trees can get you there, but are less convenient.
Suresh Venkat
CC BY-SA 3.0
2011-10-05T14:55:03.013Z
@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.
Noldorin
CC BY-SA 3.0
2011-10-05T14:57:29.017Z
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.
Noldorin
<ds.data-structures><tree>
Why would one ever use an Octree over a KD-tree?
Noldorin
# Why would one ever use an Octree over a KD-tree?

(Asked by: username_0 on 2011-10-04)

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.

**Tags:** ds.data-structures, tree

> **Comments:**
> **username_0**: 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?  
> **username_1**: One note is that kd-trees have guaranteed small depth. Compressed quad trees can get you there, but are less convenient.  
> **username_0**: @username_1: 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.  
> **username_0**: 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.  

---

## 4 answers

### Answer by username_2 on 2012-06-12. Score: 31

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

> **Comments:**
> **username_3**: See Sariel Har-Peled's recent textbook for a modern summary of compressed quadtrees.  
> **username_0**: 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.  
> **username_2**: 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).  
> **username_0**: I missed the "cells in". Makes sense now.  

---

### Answer by username_4 on 2011-10-05. Score: 18

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.

> **Comments:**
> **username_0**: 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...  
> **username_4**: 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.  
> **username_0**: 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...  
> **username_5**: 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.  

---

### Answer by username_6 on 2012-06-12. Score: 9

> 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](http://en.wikipedia.org/wiki/Trie) 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](http://en.wikipedia.org/wiki/Trie) 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.

> **Comments:**
> **username_0**: "octrees are tries"? Also, what do you mean by "handles heterogeneity better"? Homogeneous isn't a word I've encountered with respect to trees.  
> **username_3**: "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.  
> **username_6**: @username_0 "octrees are tries". Yes. Do you know what a trie is? http://en.wikipedia.org/wiki/Trie  
> **username_6**: @username_0 "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.  
> **username_6**: @JɛﬀE "Rebalancing an octtree is simply impossible". That's exactly what I was referring to. Apologies if my wording was confusing.  
> **username_0**: @JonHarrop: Ah right; that makes perfect sense now, ta.  
> **username_3**: _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!)._ — No, you call it a compressed octtree.  Again, see Har-Peled's book for an up-to-date discussion.  
> **username_6**: @JɛﬀE The contents of that book doesn't list anything on octrees and only one chapter on quadtrees and it doesn't mention compression in its title. How many pages are devoted to compressed quadtrees?  

---

### Answer by username_7 on 2011-10-05. Score: 3

Octrees are useful as a base datatype for continuum models, see for example the [Gerris](http://gfs.sourceforge.net/wiki/index.php/Main_Page) 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!

> **Comments:**
> **username_0**: 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?  

---

