  Given a set of $n$ points in the plane, and a parameter $k$, we consider the
problem of computing the minimum (perimeter or area) axis-aligned rectangle
enclosing $k$ points. We present the first near quadratic time algorithm for
this problem, improving over the previous near-$O(n^{5/2})$-time algorithm by
Kaplan etal [KRS17]. We provide an almost matching conditional lower bound,
under the assumption that $(\min,+)$-convolution cannot be solved in truly
subquadratic time. Furthermore, we present a new reduction (for either
perimeter or area) that can make the time bound sensitive to $k$, giving near
$O(n k) $ time. We also present a near linear time
$(1+\varepsilon)$-approximation algorithm to the minimum area of the optimal
rectangle containing $k$ points. In addition, we study related problems
including the $3$-sided, arbitrarily oriented, weighted, and subset sum
versions of the problem.
