Find a largest cube contained in the union of cuboids

Question

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.

Answer 1

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.

Answer 2

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.