Covering many points with a small-area box

Abstract

Let $P$ be a set of $n$ points in the plane. We show how to find, for a given integer $k>0$, the smallest-area axis-parallel rectangle that covers $k$ points of $P$ in $O(n{k}^2\log n+n{\log }^{2}n)$ time. We also consider the problem of, given a value $\alpha >0$, covering as many points of $P$ as possible with an axis-parallel rectangle of area at most $\alpha$. For this problem we give a probabilistic $(1-\epsilon )$-approximation that works in near-linear time: In $O((n/{\epsilon }^4){\log }^{3}n\log (1/\epsilon ))$ time we find an axis-parallel rectangle of area at most $\alpha$ that, with high probability, covers at least $(1-\epsilon ){\kappa }^{\ast }$ points, where ${\kappa }^{\ast }$ is the maximum possible number of points that could be covered.

Cited by in corpus (1)

• Minimum Enclosing Parallelogram with Outliers