An aligned rectangle is a rectangle in with its sides parallel to the and axes. Suppose you have a collection of aligned rectangles. What is the maximum value of for which it is always possible to find either disjoint rectangles in the collection or a point in that is contained in rectangles from the collection? For convenience we shall assume throughout the discussion that all rectangles are closed.

A simple example shows that cannot be greater than : one simply takes sets of aligned rectangles and makes sure that two aligned rectangles in the same set intersect, while two aligned rectangles in different sets are disjoint.

Now let us match this lower bound with an upper bound that is the same—apart from a logarithmic factor.

First, if is an aligned rectangle, let us define and to be the minimum and maximum coordinates of points in , respectively. Similarly, let and be the minimum and maximum coordinates. (Thus, if is closed, then it equals . Now, given any collection of aligned rectangles, let be the set of all real numbers that are equal to or for some in the collection, and let be the same thing for coordinates. Then the sizes of and are both at most .

Now whether or not two rectangles and intersect depends solely on the ordering of the four numbers , , and and the ordering of the four numbers , , and . Therefore, we can replace the sets and by and for two integers and that are both at most .

What all this amounts to is that we can assume, without loss of generality, that the coordinates of the vertices of all rectangles in the collection are integers between and .

Now it turns out to be a lot easier to prove the result if all the rectangles have about the same size and shape. Here is an argument that shows that gives a lower bound of for aligned squares.^◊ Let us form a graph whose vertices are the aligned squares, with an edge joining two vertices if those squares intersect. (If you are unfamiliar with graph theory terminology, then you can find it in Wikipedia's graph theory glossary.) If the maximum degree of any vertex in this graph is , then we can pick a sequence of vertices , with no vertex joined to any previous one, provided that , so certainly if . So in this case we have a collection of disjoint squares. But now suppose that there is a vertex of degree greater than . This will be a square that overlaps with over other squares. Now each of those other squares must contain a vertex of the original square (this is the step that fails when the rectangles have different shapes), so a least one vertex of must be contained in at least rectangles, which completes the proof.

What can we do if we have rectangles? We can use the widely applicable trick of making everything roughly the same size. The widths of the rectangles lie between and , as do their heights. Let us partition the set into sets of the form . There are at most of these sets, so we can find two of them, and say, and a set of at least aligned rectangles taken from the original collection, such that the width of every rectangle in lies in and the height lies in .

This implies that the ratios of the widths and heights of any two rectangles in are at most 2. We now repeat the argument above for squares, except that this time when we have a rectangle of degree at least (where is the size of ), we cannot argue that all rectangles that intersect must contain a vertex of . However, we can argue that any rectangle in that intersects contains either a vertex of or the midpoint of an edge or the centre of . This makes nine possibilities, so we can obtain a lower bound of . Since is of the form , this gives a lower bound of the form for the original problem.

This demonstrates one way in which stray logarithmic factors can arise: through an application of the make-everything-roughly-the-same-size trick.

It is often possible to be more careful and remove a logarithmic factor of this kind by avoiding the use of that trick and thinking hard about how to relate objects of different sizes. However, closing the gap between the above estimates is still an open problem.