18
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – pantoffski Mar 2 '11 at 5:31
8
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.