question

Suppose we want to perform operations on a set of Body objects in space. For example, perhaps we wanted to ask questions about the Sun bodies (shown as yellow dots below) in our two-dimension image space.
How many objects are in a region?

HashTable

iterate over all items to check
problem: totally random!

uniform partitioning

Our attempt is to ensure that the bucket numbers depend only on position!
uniformly partition our image space by throwing a 4x4 grid over it (“spatial hashing”)
implementation: provide a getX() and getY() function.
On average, the runtime will be 16 times faster than without spatial partitioning, but unfortunately 𝑁/16 is still Θ(N). BUT, this does indeed work better in practice.

QuadTrees

Key advantage that BST better than HashTable is that the trees track the order of items.
However, the objects in multiple dimensions can be both “lesser” and “greater” than the other subject.
Therefore, we choose to separate the tree children into 4.
![[Pasted image 20240515230236.png]]
Here, we see that node A splits its surrounding area into a northwest, northeast, southeast, and southwest region. Since E resides in the northeast quadrant of A, when we insert E, we can put it as a child of A as its NE child.

higher dimension: KD Tree

It works by rotating through all the dimensions level by level.

construction

Take 2-dimension tree as an example: X-based tree at the first level, and then the Y-based tree on the second level, and then the X-based tree at the third level…
a K-D tree will always be a binary tree, since each level is partitioned into “greater” and “less than”.

search

Start at the root and store that point as the “best so far”. Compute its distance to the query point, and save that as the “score to beat”.
This node partitions the space around it into two subspaces. For each subspace, computing the shortest distance between the query point and the edge of our subspace.
Continue recursively for each subspace identified as containing a possibly better point.
![[Pasted image 20240515231753.png]]