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!

combinatorial complexity. Anything that's not on Wikipedia is worth defining for completeness. $\endgroup$ – Igor Pak Jul 4 '13 at 23:11