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

<p>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.</p>

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

<p>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.</p>

<p>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.</p>

<p>[In the ref I gave, they mention that [17] 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.]</p>

CC BY-SA 3.0
2016-05-11T21:22:15.197Z
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
CC BY-SA 3.0
2016-05-10T22:02:20.050Z
2016-05-10T22:13:10.663Z
2016-05-10T22:13:10.663Z
Sariel Har-Peled
<p>Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-05-09T21:36:07.273Z
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
CC BY-SA 3.0
2016-05-12T03:21:48.097Z
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
CC BY-SA 3.0
2016-05-12T03:25:16.223Z
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
<cg.comp-geom>
Smallest axis-aligned box that contains $k$ points
GMB
# Smallest axis-aligned box that contains $k$ points

(Asked by: username_0 on 2016-05-09)

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.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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...  
> **username_2**: 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.,..  

---

## 1 answers

### Answer by username_2 on 2016-05-10. Score: 11

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 [17] 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.]

> **Comments:**
> **username_0**: 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 ...  

---

