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|$)?

  • $\begingroup$ Have you tried using inclusion-exclusion? $\endgroup$ – Gerry Myerson Apr 1 '11 at 5:25
  • $\begingroup$ 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. $\endgroup$ – 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.

It is possible that this breaks down for an infinite number of rectangles, but I don't see how yet.

Gerhard "Ask Me About System Design" Paseman, 2011.04.01

  • $\begingroup$ 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. $\endgroup$ – Juris Steprans Apr 1 '11 at 16:19
  • $\begingroup$ If we view it in terms of raw cardinality of the point set, then I agree. Lately, I have had posters change/generalize their questions on me. So I am half prepared to see cardinality replaced by some measure. I still think the argument works because of the shape of the covering set (it is false for non-convex sets, and I am unsure about general rectangles) for infinitely many rectangles. Gerhard "Get Ready, Get Set, Generalize!" Paseman, 2011.04.01 $\endgroup$ – Gerhard Paseman Apr 1 '11 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.