Monday, February 12, 2018
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
In 1918, Karl Reinhardt asked which convex polygon can tile the plane, and the pentagons was the only opened case. Fifteen types of such pentagons have been found between 1918 and 2015.
I present an exhaustive search of all families of convex pentagons which tile the plane. This proof is in two parts. First we show that if a pentagon tiles the plane, then it is in one of 371 families. Then a computer program tries, for each family, all possible tile arrangement, and shows that there are no more than the already known fifteen types. In particular, this implies that there is no convex polygon which allows only non-periodic tilings.
Colloquium - 16:00
We compute the number of triangulations of a convex k-gon with subdivided sides for the following cases: (1) all the sides are subdivided by the same number of points (r); (2) k=3. We find explicit formulas and generating functions, and we determine the asymptotic behaviour of these numbers as k and/or r tend to infinity. Finally, we link these results to a well-known open problem from computational geometry: finding a planar set of n points in general position that has the minimum possible number of triangulations.
joint work with C. Krattenthaler and T. Mansour