Home Bookmarks Papers Blog

Smallest $k$-enclosing rectangle revisited $\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$


Timothy M. Chan, and Sariel Har-Peled.
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+\eps)$-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.
PDF.
Slides: PDF.
Last modified: Mon 2019-06-17 03:26:59 UTC 2019 by Sariel Har-Peled