<p>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 $&lt;0$ with an assignment of 0 for that variable and $&gt;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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-02T13:35:52.867Z
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
CC BY-SA 2.5
2011-03-02T11:06:51.527Z
2011-03-02T11:06:51.527Z
Joe Fitzsimons
<p>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...</p>

<p>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: <a href="http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf" rel="nofollow">http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf</a>, this can be done in $O(n^{2+\varepsilon})$ time, for an arbitrary small constant $\varepsilon &gt; 0$. </p>

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

CC BY-SA 2.5
2011-03-02T05:31:26.437Z
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 http://www.inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf). The 3D case with only boxes shouldn't be much difficult.
pantoffski
CC BY-SA 2.5
2011-03-01T05:13:21.627Z
2011-03-01T05:21:16.333Z
2011-03-01T05:21:16.333Z
Sariel Har-Peled
<p>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? </p>

<p>For instance,
If I have the following cuboids: </p>

<ul>
<li>a cuboid starting at (0,0,0) with size (10,10,10),</li>
<li>a cuboid at (10,0,0) with size (12,13,15),</li>
<li>a cuboid at (0,10,0) with size (10,10,10),</li>
<li>a cuboid at (0,0,10) with size (10,10,10), and</li>
<li>a cuboid at (10,10,10) with size (9,9,9).</li>
</ul>

<p>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).</p>

<p>A more general version of this question: </p>

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

CC BY-SA 2.5
2011-02-28T00:37:34.523Z
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
CC BY-SA 2.5
2011-02-28T03:10:59.143Z
Can these cuboids overlap?
Peter Boothe
CC BY-SA 2.5
2011-02-28T06:06:43.887Z
@Suresh, thanks for clarify & generalize the question :)
@Peter, in my case... It won't overlap :)
pantoffski
CC BY-SA 2.5
2011-03-01T17:30:21.043Z
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
CC BY-SA 2.5
2011-03-02T05:36:09.617Z
In my case, each cuboid's face are orthogonal to the axes only.
pantoffski
<ds.algorithms><cg.comp-geom>
Find a largest cube contained in the union of cuboids
pantoffski
# Find a largest cube contained in the union of cuboids

(Asked by: username_0 on 2011-02-27)

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.

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: 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.  
> **username_2**: Can these cuboids overlap?  
> **username_0**: @Suresh, thanks for clarify & generalize the question :) @Peter, in my case... It won't overlap :)  
> **username_3**: 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.  
> **username_0**: In my case, each cuboid's face are orthogonal to the axes only.  

---

## 2 answers

### Answer by username_4 on 2011-03-01. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 http://www.inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf). The 3D case with only boxes shouldn't be much difficult.  

---

### Answer by username_3 on 2011-03-02. Score: 8

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.

> **Comments:**
> **username_3**: 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.  

---

