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.
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 &gt; 0$. 

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