11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh May 9 '16 at 21:36
  • $\begingroup$ 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... $\endgroup$ – Sariel Har-Peled May 12 '16 at 3:21
  • $\begingroup$ 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.,.. $\endgroup$ – Sariel Har-Peled May 12 '16 at 3:25
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ... $\endgroup$ – GMB May 11 '16 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.