#computing ### Octree ![[Octree.png]] Imagine, someday, you lose your wallet. You remember having it until you came back home by driving. You will therefore search for your wallet around your car, you won’t search the whole universe to find your wallet, right ? That’s the principle of an **Octree** data structure. At first I did the “search the whole universe” solution in order to see if objects are overlapping (collision) because it’s the easy solution to implement, but as you will suppose, it’s inefficient, we say $O(n²)$ time complexity to find an element however $O(log^n)$ using the **Octree** data structure. **Concretely, using a Octree is a way to efficiently manage data in three dimensions.**