Covering many points with a small-area box

Mark de Berg, Sergio Cabello, Otfried Cheong +2

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 \log…