Let's say you have a bunch of points in a space, like in the maps above. Someone asks you if some arbitrary point *p* is within your bunch of points. How can you find out if you have that point?

You could compare every single point you have to *p*, but if you had 1000 points, and none of them were *p*, you'd have to do 1000 comparisons to find that out. Alternatively, you could get very fast lookup by keeping a grid (a 2D array) of booleans for every single possible point in this space. However, if the space these points are on is 1,000,000 x 1,000,000, you need to store 1,000,000,000,000 variables.

Or you could set up a quadtree. When you have it search for *p*, it will find out which quadrant it is inside. Then, it will find out what quadrant within that quadrant it is inside. And so forth.

It will only have to do this at most seven times for a 100x100 space (assuming points can only have integer values), even if there are 1000 points in it. For a 1,000,000x1,000,000 space, it's a maximum of 20 times.

After it finds its way to that rectangle node, it merely needs to see if any of the four children equal *p*.

Again, let's say you have a bunch of points in a space. Rather than ask you whether any of them match a given point, someone asks you what the nearest point you have to an arbitrary point among your points.

With a quadtree, while searching, you can say, "OK, there's no way anything in this quadrant has any chance of being the nearest neighbor" and eliminate a lot of point comparisons that way. Patrick Surry has a good example of that.