It is a remarkable fact that the union of congrent cubes has only at most near-quadratic combinatorial complexity, $O^*(n^2)$ for $n$ cubes, known to be almost tight. This contrasts with the union of congruent rectangular boxes, which can have cubic complexity, $\Omega(n^3)$. The "fatness" of cubes in comparison to boxes accounts for the lower complexity. (In response to Igor's reasonable request: By combinatorial complexity I mean the the total number of vertices, edges, and faces of the nonconvex polyhedron that is the union of the cubes. Of course, $\{V, E, F\}$ are interrelated by Euler's formula. An edge of a cube is in general fractured into many edges in the polyhedron that constitutes the union. Where a cube edge penetrates another cube face, it constitutes a vertex of the union. Most faces of the union are nonconvex.) The upperbound was first established in this paper:

János Pach, Ido Safruti, and Micha Sharir. "The union of congruent cubes in three dimensions." Proceedings 17th Symposium Computational Geometry. ACM, 2001. (ACM link)

I am considering the special case of congrent cubes all centered on the origin. Still I believe the quadratic complexity can be realized, as illustrated left below. But I wonder if the complexity of a random union, right below, has lower complexity, perhaps $O(n \log n)$?
By a "random union" I mean that each cube is rotated about the origin by a random orthogonal matrix, chosen uniformly. If anyone can see a simple argument to establish bounds on expected complexity, or can point me to related work in this direction, I'd appreciate it—Thanks!

  • $\begingroup$ Joe, consider explaining what is combinatorial complexity. Anything that's not on Wikipedia is worth defining for completeness. $\endgroup$ – Igor Pak Jul 4 '13 at 23:11
  • $\begingroup$ Thanks, Igor, you are right, the meaning is not obvious. Tried to clarify... $\endgroup$ – Joseph O'Rourke Jul 4 '13 at 23:45

I wonder where $\log n$ came from. I'm getting just $n$. Can you spot any errors in the argument below?

I'll assume that the distance from the origin to each cube vertex is $1$.

Claim 1: Let $x$ be any point with $|x|<1$. Assume that $r\approx \frac{1-|x|}{10}$. Then the probability that the surface of the randomly rotated cube intersects the ball $B(x,r)$ and the probability that its edge intersects the ball are at most $Cr^2\approx C(1-|x|)^2$, and the probability that it covers the ball is at least $cr^2\approx c(1-|x|)^2$

Proof: just look at the part of the sphere of radius about $1-|x|$ that is inside the cube.

Claim 2: It is enough to count the edge ends.

Proof: $V+F+E=2E+2$ and nobody cares about $2$.

Claim 3: The ball $B(0,1)$ can be covered by balls $B(x,r)$ such that

a) All $r$ are of the kind $r=2^{-k}\in (0,1)$

b) For every ball, $r\approx \frac{1-|x|}{10}$

b) There are about $r^{-2}$ balls of any fixed radius $r$ in the covering.

Proof: Look up "Whitney decomposition" on Google.

Claim 4: Every edge end inside $B(0,1)$ is either an intersection of 3 faces or of an edge and a face.

Proof: What else can it be?

Claim 5: The expected number of edge ends in $B(x,r)$ is at most $Cn^2 r^4(1-c r^2)^{n-2}+Cn^3 r^6(1-c r^2)^{n-3}$.

Proof: Either one cube must have an edge crossing the ball, the surface of another one should intersect the ball, and the rest should not cover the ball, or 3 cube surfaces should intersect the ball and the rest should not cover it.

Claim 6: The total expected number of edge ends is at most $8n+Cn\sum_r\left[n r^2(1-c r^2)^{n-2}+n^2 r^4(1-c r^2)^{n-3}\right]$.

Proof: The additivity of expectation ($8n$ is the number of vertices on the unit sphere).

Claim 8: For every $k\ge 1, n\ge 2k+2$, we have $$ \sum_r n^kr^{2k}(1-cr^2)^{n-k-1}\le C_k $$

Proof: Geometric growth for $r^2<n^{-1}$, double exponential decay beyond that. Thus, only a constant number of terms with $r^2\approx n^{-1}$ matter whence the estimate.

Claim 9: The average complexity is of order $n$.

Proof: We certainly have $8n$ vertices. On the other hand, we have at most $Cn$ edge ends for $n\ge 6$. So, we are fine from both below and above.

  • $\begingroup$ This is a sophisticated argument--impressive! I am pleased to learn of the Whitney decomposition. I certainly don't see any holes in your proof. It was only a guess (by analogy with hulls of random points) that $\log n$ would appear. $\endgroup$ – Joseph O'Rourke Aug 24 '13 at 13:55

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.