Bachelor thesis : Überdeckung der Ebene durch Kreispackungen

Leszek Mysliwiec

Advisor: Prof. Dr. Günter Rote

Mit einer Menge von disjunkten Kreisen kann man die Ebene nicht vollständig ausfüllen, selbst wenn man unendlich viele Kreise verwendet (siehe Abbildung).

Selbst wenn man alle Kreise um den Faktor 1.00001 von ihrem Mittelpunkt aus aufbläst, wird die Ebene nicht überdeckt (es sei denn, die Packung enthält unbeschränkt große Kreise). In dieser Arbeit sollen die Parameter des Beweises dieser Aussagesorgfältig eingestellt werden, damit der Vergrößerungsfaktor größer wird, wobei der Beweis immer noch funktionieren und vielleicht sogar noch einfacher werden soll.

Diese Untersuchungen spielen eine Rolle beim Entwurf von guten Verbindungsnetzen in der Ebene, bei denen der "Umweg" zwischen zwei beliebigen Punkten des Netzes, bezogen auf die Luftlinie, nicht zu groß werden soll.