The structure
A quadtree is a tree where every node covers a rectangular region and has up to four children, one per quadrant. A node splits into four when the number of points inside it crosses a capacity threshold. Sparse regions stay as large leaves while dense city centers split deeply.
Why adapt to density
- Uniform grids waste space in empty areas and overflow in busy ones.
- A quadtree gives each leaf a bounded number of points, so a query touches only a few well sized cells.
- It naturally answers range and nearest neighbor queries by descending only into nodes that overlap the search window.
Searching nearby
To find points near a location, walk down to the leaf containing it, then expand outward into sibling and neighbor leaves until enough candidates are collected.
Key idea
A quadtree subdivides space only where points are dense, keeping every leaf small and proximity queries cheap.