I have a lot of cuboids in 3D space, each has a starting point at (x,y,z) and has size of (Lx,Ly,Lz). I wonder how to find a largest cube in this 3D space that is contained in the union of the cuboids. Is there an efficient algorithm for this?

For instance, If I have the following cuboids:

  • a cuboid starting at (0,0,0) with size (10,10,10),
  • a cuboid at (10,0,0) with size (12,13,15),
  • a cuboid at (0,10,0) with size (10,10,10),
  • a cuboid at (0,0,10) with size (10,10,10), and
  • a cuboid at (10,10,10) with size (9,9,9).

Then, the largest cube contained in the union of these cuboids will be a cube starting at (0,0,0) with size (19,19,19).

A more general version of this question:

Given a collection of $n$ boxes in $\mathbb{R}^d$, find the largest hypercube contained within the union of the boxes.

  • 8
    $\begingroup$ I think there's a better question hidden inside: namely, given a union of boxes in $R^d$, compute the largest hypercube contained within the union. $\endgroup$ Feb 28, 2011 at 0:37
  • 1
    $\begingroup$ Can these cuboids overlap? $\endgroup$ Feb 28, 2011 at 3:10
  • $\begingroup$ @Suresh, thanks for clarify & generalize the question :) @Peter, in my case... It won't overlap :) $\endgroup$
    – pantoffski
    Feb 28, 2011 at 6:06
  • 2
    $\begingroup$ The way you have phesed this, it sounds like the sides of the cubes are aligned with the x, y and z axes. Is this the case, or can the cubes have arbitrary orientations? This obviously makes a significant difference to the efficiency of the algorithm. $\endgroup$ Mar 1, 2011 at 17:30
  • $\begingroup$ In my case, each cuboid's face are orthogonal to the axes only. $\endgroup$
    – pantoffski
    Mar 2, 2011 at 5:36

2 Answers 2


Well, here is an first try silly answer... Take a plane through each face of of the rectangular boxes. This form a grid of size $O(n^3)$. It is not hard to compute for each such grid cell whether its inside the union or outside. Now, from each grid vertex, grow a cube (having this vertex as a vertex) trying to make it as large as possible. Doing it in the most naive way, this takes $O(n^3 \log n)$ time per vertex, but probably using orthogonal range searching magic, one should be able to do it in $\log^{O(1)} n$ per vertex. So $O(n^3 \log^{O(1)} n )$ should be possible...

A second try: Compute the union. In this specific case, this can be done in $O( n \log n)$ time (by sweeping planes). Now, observe that you just need to compute the $L_\infty$ voronoi diagram of the boundary of the union. Using the result: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf, this can be done in $O(n^{2+\varepsilon})$ time, for an arbitrary small constant $\varepsilon > 0$.

Breaking the $O(n^2)$ running time bound here would be interesting, IMHO.

  • $\begingroup$ Thank you sir, I also think L∞ is a best solution for this problem so far. Since I've done the L∞ for 2D case before (implemented by methods provided in this paper inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf). The 3D case with only boxes shouldn't be much difficult. $\endgroup$
    – pantoffski
    Mar 2, 2011 at 5:31

The answer to the general question about $R^d$ would seem to be that it is NP-hard. The proof is fairly simple. We simply take a 3SAT instance on $d$ variables and associate each variable with a dimension. Think of the space as a space of possible assignments of variables: we only consider points between -1 and +1 in each dimesnion, and associate locations $<0$ with an assignment of 0 for that variable and $>0$ with an assignment of 1. Each clause excludes a region given by a $1 \times 1 \times 1 \times n \times n \times n ... \times n$ hypercuboid.

If the union of these cuboids fills the space (and so contains a $2 \times 2 \times ... \times 2$ cube), then there is no satisfying assignment of variables for the 3SAT instance. If however the largest cube contained is $1 \times 1 \times ... \times 1$ or 0 (for no clauses), the only other possibilities, then a satisfying assignment of variables exists.

  • $\begingroup$ I imagine you can prove it is in FNP (at least in the case of axes-aligned cuboids), by running the above arguement in reverse and showing that any cuboid constitutes a constraint which can be checked in polynomial time. $\endgroup$ Mar 2, 2011 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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