Archive of posts with tag 'BorisAronov'

• Boris Aronov, The complexity of unions of shapes

  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).</p>

  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