## Octrees We define the unit cube $[0, 1]^3\in\mathbb{R}^3$. An Octree is a tree-like subdivision of the unit cube in which each internal node has exactly eight child cubes. A node without children is called a leaf. We identify a node of the octree with the associated subcube of $[0, 1]^3$. ## Quadtrees A quadtree is the two-dimensional correspondence of an octree. It is tree-like partition of the unit square $[0, 1]^2\in\mathbb{R}^2$ in which each internal node has exactly four child cubes. We use the following definitions. - $N$ denotes a given node of the tree. - The root of the tree is denoted by $R$. - The number of edges to go from the root to a given node N is called the level $\mathcal{L}(N)$ of the node $N$. The root has level $0$. - The maximum level of the tree is denoted by $\mathcal{L}^*$. - The parent of a node $N$ is denoted by $\mathcal{P}(N)$. - The siblings of a node $N$ are all nodes $\mathcal{S}(N)$ with the same parent as $N$. By definition we define that $N\in\mathcal{S}(N)$. - The direct children of a node $N$ are denoted by $\mathcal{C}(N)$. - The set of leafs of an octree is denoted by $\mathcal{L}$. - The set of all descendents of a node $N$ is called $\mathcal{D}(N)$. - The set of all neighbours $\mathcal{N}(N)$ consists of all nodes whose associated cube share at least a vertex with the cube associated with the node $N$. An octree/quadtree is called *uniform* if all leafs have the same level. Below is an example of a quadtree with maximum level $\mathcal{L}^*=2$. The geometric partitioning on each level together with the associated quadtree are shown. On the root level the tree consists of a single point. ![[Octrees and Quadtrees 2024-12-02 09.10.24.excalidraw.png]] ## Balanced trees *An octree/quadtree is k-balanced if and only if for any $\ell\in [1, \mathcal{L}^*$] no leaf at level $\ell$ shares an m-dimensional face with another leaf at level greater than $\mathcal{\ell}+1$.* ## Morton indices [[Morton Indexing]] is an efficient way to assign a unique identifier to each box in an octree or quadtree. ## Near field and Interaction list The term near field is often used for octrees and quadtrees in the context of particle simulations. The near field of a box $N$ is simply the set of all neighbours $\mathcal{N}(N)$. The interaction list $\mathcal{I}(N)$ consists of the children of the neighbours of $\mathcal{P}(N)$ that are not neighbours of $N$. Below we show near field (red) and interaction list (blue) of the green box at various levels. A box on level 1 cannot have an interaction list, only a near field. ![[Structure of the Fast Multipole Method 2024-11-24 10.42.32.excalidraw.png]] ## References 1. Sundar, H., Sampath, R. S. & Biros, G. Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel. _SIAM J. Sci. Comput._ **30**, 2675–2708 (2008).