Skip to main content
corrected spelling
Source Link

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

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

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

Source Link

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