Complexity of the union of randomly rotated unit cubes

Question

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!

Answer 1

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.