## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

No Title

The Union of Geometric Objects and Generalized Voronoi Diagrams

Micha Sharir, Tel Aviv University

Let be a collection of n objects in d-space, and let U denote the union of . The combinatorial complexity of U is the number of faces, of all dimensions, of the arrangement of the boundary surfaces of the objects in (e.g., a vertex is an intersection of d boudaries). If each of the objects in has constant description complexity' then the complexity of U is O(nd) and in general this bound is tight.

We analyze the complexity of U in several special cases, where we can obtain a smaller complexity bound. There are many such instances in the 2-dimensional case (pseudo-disks, fat objects), but the problem is quite hard in 3 and more dimensions.

The cases that we consider include convex polyhedra in 3 dimensions, axis-parallel cubes in any dimension, infinite congruent cylinders in 3 dimensions, and more.

A special important case is the union of Minkowski sums: Our objects are of the form , where the Ai's are convex pairwise-disjoint objects and B is another convex object, and denotes the Minkowski sum of X and Y.

The boundary of such a union can be regarded as a cross-section or a level-set' of the generalized Voronoi diagram with the Ai's as sites and with the metric (or convex distance function) induced by B as a `unit ball': The union boundary is the locus of points whose B-distance from the nearest site is exactly 1.

We discuss a few cases where sharper bounds are known either for the complexity of the union of Minkowski sums, as above, or for the complexity of the associated Voronoi diagram (a much harder problem).

Back