THE UNION OF CONVEX POLYHEDRA IN 3 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 exis t collections of polyhedra with Omega(k(3) + kn alpha(k)) union comple xity. We also describe a rather simple randomized incremental algorith m for computing the boundary of the union in O(k(3) + kn log k log n) expected time.