[Mittagsseminar TI] Mittagsseminar am Dienstag, 30.1. und Donnerstag, 1.2.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 30.1.2024, 12:00 Uhr, SR 051, Takustraße 9
Ji Hoon Chun (TU Berlin)
zum Thema: Exact covering with unit disks
und am
Donnerstag, 1.1.2024, 12:00 Uhr, SR 051, Takustraße 9
Günter Rote
zum Thema: Hilbert10.1: A Diophantine relation for exponential growth
Zusammenfassung für den Vortrag am Dienstag:
Exact covering with unit disks
==============================
Abstract:
In 2008, puzzle designer Naoki Inaba introduced the following problem: Show that any set
of 10 points in R^2 can be covered by non-overlapping unit disks. We provide an overview
of existing work towards finding the maximum number of points that can always be covered
in this way. Then we present a variation of this problem where a given point set in the
plane is covered by possibly overlapping unit disks so that each point is covered exactly
once. We outline a proof showing that 17 points can always be exactly covered and a
construction of a 657-point set where an exact cover is not possible.
