Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**
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*(*n*^{d}) 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 *A*_{i}'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 *A*_{i}'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