There is a set of $n$ points in the 2-dimensional plane. All x values and all y values are different. We want to draw the largest set of axis-parallel rectangles such that:
- All rectangles are pairwise interior-disjoint.
- Every rectangle has (at least) two points at opposite corners.
The number of possible rectangles is obviously related to the locations of the points. Here are two examples with $n=8$:
$n-1$ is probably the worst case (fewest possible rectangles), as we can always order the points according to their $x$ axis and draw a rectangle between point $i$ to point $i+1$.
MY QUESTION IS: What is the best case - i.e. the largest number of rectangles possible, as a function of $n$?