Covering many points with a small-area box

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(nk 2 logn+nlog 2 n) time. We also consider the problem of, given a value α>0 , covering as many points of P as possible with an axis-parallel rectangle of area at most α . For this problem we give a randomized (1−ε) -approximation that works in near-linear time: in O((n/ε 4 )log 3 nlog(1/ε)) time we find an axis-parallel rectangle of area at most α that covers at least (1−ε)κ ∗ points, where κ ∗ is the maximum possible number of points that could be covered