Theory of Combinatorial Algorithms, Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich

No Title

The Union of Geometric Objects and Generalized Voronoi Diagrams

Micha Sharir, Tel Aviv University

Let ${\cal C}$ be a collection of n objects in d-space, and let U denote the union of ${\cal C}$ . The combinatorial complexity of U is the number of faces, of all dimensions, of the arrangement of the boundary surfaces of the objects in ${\cal C}$ (e.g., a vertex is an intersection of d boudaries). If each of the objects in ${\cal C}$ 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 $\{ A_i \oplus B\}_{i=1}^n$ , where the A_i's are convex pairwise-disjoint objects and B is another convex object, and $X\oplus Y$ 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