# What is the problem in "closest pair problem" if all points share the same x-coordinate

The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large number of points.

I just don't know why, I heard the running time becomes $n^2$

What about it? What is the problem, since the proof for the algorithm shows, that at max. 8 points can reside in the $2 \delta \times \delta$ area.

• I think you may be confused. $n^2$ is brute force... Nov 17 '11 at 22:12
• Yes I know that. But if all points share the same x-coordinate, all the points land in the same set in the deivide step, don't they? Nov 17 '11 at 22:35