The complexity of unions of shapes

Boris Aronov
Department of Computer Science and Engineering

Polytechnic Institute of NYU

2013/12/20 Friday 4PM-5PM

Room 1409

Over the years, the following class of problems has been studied quite a lot: Given a class of simply-shaped objects in the plane (disks, unit disks, squares, axis-aligned squares, isosceles triangles, shapes definable with a small number of polynomial equations and inequalities), how complicated can be the union of N shapes from the class? There are several different ways in which one can measure this (combinatorial) complexity. Two popular measures are the number of connected components of the complement, and the number of places where two object boundaries intersect on the boundary of the union (so-called “vertices” of the union).

It is easy to see that, if each object is “simple,” the union of N objects cannot be larger than O(N^2) and a matching construction is easy. Are there classes of objects for which this quantity is near-linear in N? (Yes, there are: disks, axis-aligned squares, and more.) The quest for such classes, over the years, motivation for the problem, generalizations to higher dimensions, and other puzzles will constitute the content of this talk.

If I ever get to it, the latest and most amazing result in this area is joint work with Mark de Berg, Esther Ezra, and Micha Sharir. It is quite technical and I will not be able to say much about this during the talk, but if anyone is interested, I can provide lots of technical details on request. An overview of the subject will be mostly based on a survey of Agarwal, Pach, and Sharir.

Tags: BorisAronov

This entry was posted on Wednesday, December 18th, 2013 at 11:52 am and is filed under 2013, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.