Boris Aronov (Polytechnic Institute of NYU)
Combinatorial complexity of unions of objects
We will discuss a class of problems that are loosely called "the complexity of unions of objects." Consider a collection of N "nice" geometric objects in the plane, such as squares, disks, "fat" triangles, etc). Consider the boundary of the union of such a collection. It consists of maximal portions of the boundary of a single object ("edges") ending at points where object boundaries intersect ("vertices"). The number of such edges and vertices is the combinatorial complexity of the union. We study the maximum of such combinatorial complexity, as a function of N, for different classes of shapes, mostly in the plane. We will start with several motivating examples, then state the general problem and provide some historical perspective on how the problem evolved. I will end with an update to the cutting-edge results in the field. Several tantalizing open problems will be mentioned.
The content of this talk is loosely based on a 2008 survey "State of the union (of geometric objects)" by Agarwal, Sharir, and Pach, and the speaker"s own involvement in the subject. Motivation, examples, and sketches of the easier proofs will be provided. The discussion will be largely limited to two dimensions due to the speaker"s inability to draw anything complicated.
| 26.02.2013 | |