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(k3 + 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(k3 + kn log k log n) expected time.

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions.Specifically, if S is a set of n points in general position in Jf?-d, the complexity of its Voronoi diagram under the Lm metric, and also under a simplicial distance function, are both shown to be qn[dlzl ).The upper bound for the case of the Lm metric folIows from a new upper bound, also proved in this paper, on the complexity of the union of n axis-parallel hypercubes in Eld.This complexity is @(n ~d/21 ), for d > 1, and it improves to @(nld/2J ), for d ~2, if all the hypercubes have the same size.Under the L1 metric, the complexity of the Voronoi diagram of a set of n points in general position in IR3 is shown to be @(n2 ).We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations.

We present a simple but powerful new probabilistic technique for analyzing the combinatorial complexity of various substructures in arrangements of piecewilinear surfaces in higher dimensions.We apply the technique (a) to derive new and simpler proofs of the known bounds on the complexity of the lower envelope, of a single cell, or of a zone in arrangements of simplicee in higher dimensions, and (b) to obtain improved bounds on the complexity of the vertical decomposition of a single cell in an arrangement of triangles in 3-space, and of several other substructures in such an arrangement (the entire arrangement, all nonconvex cells, and any collection of cells).The latter results also lead to improved algorithms for computing substructures in arrangements of triangles.