Split a square into four whenever it holds too many points: a 4-way tree for points in the plane, with range queries that skip whole squares.
This interactive visualization needs JavaScript.