# Smallest axis-aligned box that contains $k$ points

Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.

Output: The smallest volume axis-aligned bounding box that contains at least $k$ of these $n$ points.

I'm wondering if any algorithms are known for this problem. The best I could think of was $O(n^5)$ time, loosely as follows: brute-force over all possible upper and lower bounds for two of the three dimensions; for each of these $O(n^4)$ possibilities, we can solve the corresponding $1$-dimensional version of the problem in $O(n)$ time using a sliding window algorithm.

• Can't we compute a table of size $n^3$ for the number of points $p$ with $p.x< x, p.y<y, p.z <z$? Computing the number of points and the volume can be done with const number of operations, and we can use dynamic programming with a table of size $k n^3$ and should be able to get an $O(kn^3)$ algorithm. – Kaveh May 9 '16 at 21:36
• Ok. In this case, that $k=\Theta(n)$, you can not really hope to do better than $n^5$. Because, there are $n^6$ different distinct boxes, and by averaging argument (on a random value of k) there are $n^5$ boxes containing exactly k points. Unless you can somehow use the volume thingy to somehow smallify the search space, but that somehow seems optimistic... – Sariel Har-Peled May 12 '16 at 3:21
• BTW, in your case, you can get a box containing $(1-\epsilon)k$ of the points, and that is smaller than the optimal box containing $k$ points in $O( ((n/k)/\epsilon^2 \log n)^{O(1)})$ time. For $k = \Theta(n)$ this is essentially polylog time.,.. – Sariel Har-Peled May 12 '16 at 3:25

For $n$ points there are $O(n^3)$ empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs).

For your problem, take a random sample of points, where every point is picked with porbability $1/k$. Such a random sample has size (in expectation) $n/k$ [and for the sake of contradiction assume it is]. There are $O((n/k)^3)$ empty boxes having points from $R$ on their sides, by the above. For each such box, use an orthogonal range searching data-structure to compute how many points exactly it contains. Repeat this process $O(k^6 \log n)$ times. With high probability, one of the boxes you tried is the desired box.

Overall, the running time of this is $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$.

To see why this work, consider the optimal box. It has 6 points of P on its boundary. The probability that the random sample pick these six points, and none of the points inside the box is at least $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$. Thus, if you repeat the process $O( (1/p) \log n)$ times, with high probabilty one of the random samples would induce the desired box as an empty box.

Since $\Theta(n^3)$ is tight for the number of empty boxes (see intro the above paper for relevant refs), it seems unlikely that a significnatly faster algorithm is possible.

[In the ref I gave, they mention that  provides an algorithm that enumerates all maximal empty boxes among point in 3d in $O(n^3 \log^2 n)$ time, which is the black box you need for the above.]

• Thanks -- this is brilliant! A detail that I really should have mentioned (sorry!) is that $k = \Theta(n)$ for my purposes, so $O(n^3 k^3)$ is only about as good as $O(n^6)$. Still, though, there are a lot of very cool ideas here that might be useful for the large $k$ version ... – GMB May 11 '16 at 21:22