Seminars in March 2017

  • Otfried Cheong, The reverse Kakeya problem
    The reverse Kakeya problem
    Otfried Cheong
    School of Computing, KAIST
    2017/3/20 Tue 5PM
    We prove a generalization of Pal’s 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360 degrees inside Q. We also prove a lower bound of Ω(m n2) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.
    Tags:

  • [SoC Colloquium] Helmut Alt, Packing Problems: Algorithms and Complexity
    Packing Problems: Algorithms and Complexity
    Helmut Alt
    Department of Computer Science, Freie Universität Berlin
    2017/3/13 Mon 4PM-6PM
    Packing problems are concerned with positioning geometric objects so that they do not overlap and require an amount of space as small as possible. They have been investigated within mathematics for centuries starting with the famous Kepler conjecture. There are many surprising properties and open problems in connection with packing. The lecture will give a short survey about these “classical” issues but then concentrate on algorithms for packing. Since already the most simple variants are NP-hard, it makes sense to look for efficient approximation algorithms. We will present constant factor approximations for packing rectangles and convex polygons into containers which are minimum area rectangles or convex sets. Algorithms for analogous problems concerning three-dimensional objects will be presented, as well.
    This is joint research with Mark de Berg, Christian Knauer, Léonard von Niederhäusern, and Nadja Scharf.
    Tags:

  • Bernard Lidický, 3-coloring triangle-free planar graphs
    3-coloring triangle-free planar graphs
    Bernard Lidický
    Department of Mathematics, Iowa State University, Ames, IA, USA
    2017/3/7 Tue 4PM
    A well known theorem of Grötzsch states that every planar graph is 3-colorable. We will show a simple proof based on a recent result of Kostochka and Yancey on the number of edges in 4-critical graphs. Then we show a strengthening of the Grötzsch’s theorem in several different directions. Based on joint works with Ilkyoo Choi, Jan Ekstein, Zdeněk Dvořák, Přemek Holub, Alexandr Kostochka, and Matthew Yancey.
    Tags:

Monthly Archives