# Minimum cardinality of the intersection of 2D rectangles

Let $S$ be a set of 2D points $(x,y)$ with positive real coordinates, i.e. $x,y>0$. An 2D rectangle $R$ is called an ${Origin-Rectangle}$ if it is decided by the origin $(0,0)$ and another point $(x,y)$ with $x,y>0$. Denote $S_R$ as the subset of points in $S$ covered by $R$, i.e. $S_R = S\cap R$.

Now, if there exists an Origin-Rectangle $R$ such that $|S_R| \ge \alpha |S|$, where $\alpha <1$ but is very close to 1, the question is that, in the worst case (of the input), what is the minimum cardinality of the intersection of $S_R$'s for all $R$'s where $|S_R| \ge \alpha |S|$ (expressed as a fraction of $|S|$)?

• Have you tried using inclusion-exclusion? – Gerry Myerson Apr 1 '11 at 5:25
• Thanks for the reminding. Actually, after a bit more thinking later, the answer has been clear for me, which was the same as answered below. – Jiangwei Pan Apr 2 '11 at 5:52

Consider three rectangles of the type described, A,B and C, each containing $\alpha$ of the points of S, where B is such that x is smallest (or near smallest) of all rectangles containing so much of S, C is such that y is smallest, and A is somewhere in the middle. $\newcommand{frc}{2\alpha -1}$
Looking at A intersect B, I note that it should contain better than $\frc$ of the points, since A can contain at most (1- alpha) of the points of S that are not in B, and vice versa. Similarly A intersect C should contain better than $\frc$ of the points of S. Similarly B intersect C should contain better than $\frc$ of the points. Note though that B intersect C is contained inside both A intersect B and A intersect C. (This is because I chose A such that its determining point lies outside both B and C.) So the intersection of these three rectangles contains at least $\frc$ fraction of points of S. This should generalize to any finite number of rectangles.
• I don't think there is anything to consider for infinitely many rectangles. This question only makes sense for finite S and in this case the set of possible $S_R$ is also finite. Any two rectangles with the same $S_R$ are equivalent for the purposes of this question. – Juris Steprans Apr 1 '11 at 16:19