KD Trees

Two dimensions cannot be sorted for both, so partition the space and reject whole regions.

The question

Which points are inside this rectangle?

The structure responsible

KD tree

In this lab: Drag a query rectangle over real coordinates and watch subtrees get rejected without being read.

building the index…