The union of convex polyhedra in three dimensions

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k(3) + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Omega(k(3) + kn alpha(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k(3) + kn log k log n) expected time.