Complexity of the union of randomly rotated unit cubes 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!
 A: 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. 
