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), anda 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.
Find a largest cube contained in the union of cuboids
ds.algorithms;cg.comp geom
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.