Unfortunately, it's usually the case

in geometric data that the points are not evenly distributed.

It's a well-known phenomenon known as clustering that says that

the points aren't going to be evenly distributed all over the whole thing.

In the case of the grid implementation, they might all fall in the same square.

And so

the average list length is short, this is like what we encountered with hashing.

If you take all the points in one square,

in 0 and all the rest of them, your average is still N over M squared.

But they're all in that long list and

you're going to have a slower algorithm if it's based on this.

So we need a data-structure that more gracefully adapts to

the distribution of the data.

And again, it's well known that most geometric data has this kind of problem.

So for example, here's some data which is cities in the US.

It's got 13,000 points, but if you try to use the grid implementation for

this you find that half the squares would be empty and

half the points are in just 10% of the squares.

So the clustering in the data is going to make the implementation inefficient.

We need to adapt to the data.

And this is very, very typical in geometric data,

particularly in higher dimensional data, as we'll see in a minute.

So people have developed all different kinds of methods for adapting in this way.

And what we're going to look at as one of the most widely used,

which is basically to use a tree to represent a recursive

subdivision of the plain, of two-dimensional space.

It's going to be recursive, it's going to be based on the points,

the way in which we divide into halfplanes.

In this one of many different algorithms that have been studied for this.

But again it's a simple one and widely used.

So for example, if you've played the game Doom or

used a flight simulator that these types

of graphical simulations and animations are made possible.

Not only through the use of space-partitioning trees

like 2d trees and quadtrees.

And also in all different types of scientific data processing,