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