0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you tried using inclusion-exclusion? $\endgroup$
    – Gerry Myerson
    Commented Apr 1, 2011 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$
    – panjiangwei
    Commented Apr 2, 2011 at 5:52

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 1, 2011 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
    Commented Apr 1, 2011 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .