# Find a largest cube contained in the union of cuboids

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.

• 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. – Suresh Venkat Feb 28 '11 at 0:37
• Can these cuboids overlap? – Peter Boothe Feb 28 '11 at 3:10
• @Suresh, thanks for clarify & generalize the question :) @Peter, in my case... It won't overlap :) – pantoffski Feb 28 '11 at 6:06
• 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. – Joe Fitzsimons Mar 1 '11 at 17:30
• In my case, each cuboid's face are orthogonal to the axes only. – pantoffski Mar 2 '11 at 5:36

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.

• 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. – pantoffski Mar 2 '11 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.

• 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. – Joe Fitzsimons Mar 2 '11 at 13:35