Week 09 Lecture (19)

Basis for the partitioning:

a quadrant that has no sub-partitions is a leaf quadrant
each leaf quadrant maps to a single data page
subdivide until points in each quadrant fit into one data page
ideal: same number of points in each leaf quadrant (balanced)
point density varies over space
⇒ different regions require different levels of partitioning
this means that the tree is not necessarily balanced

Note: effective for d≤5, ok for 6≤d≤10, ineffective for d>10