MIT Combinatorics Seminar

Unions of Objects

Boris Aronov (Brooklyn Polytechnic University)

Wednesday, October 25, 2006   4:15 pm    Room 2-136


I will survey a class of problems with the following general theme: Given a set of N overlapping geometric objects, such as disks or squares, in the plane, consider their union. A vertex on the boundary of the union is a point where boundaries of two objects meet. The complexity of the union is the number of vertices on its boundary. Let $c(N)$ be maximum such complexity, over all possible choices of N objects. We are interested in asymptotic behavior of $c(N)$ as a function of N, for a variety of object classes, in two and higher dimensions.

Investigation of these functions has connections to geometric algorithms on the one hand and to a variety of geometric, combinatorial, and topological questions on the other.