Existenz des minimalen Umkreises für endliche Punktmengen

Der Umkreisradius ist wohldefiniert; dies sagt jedoch nichts über die Existenz eines Umkreises mit genau diesem Radius aus.
Die Existenz des minimalen Umkreises ist jedoch gesichert, falls \(\displaystyle \inf K_R=\min K_R\), also \(\displaystyle R\in K_R\) gilt. Dann gibt gibt es zu diesem Minimum einen zugeordneten Kreis. Falls \(\displaystyle K_R\) endlich ist, stimmt dies trivialerweise.
 
 

Satz C8N9 (Existenz des minimalen Umkreises für endliche Punktmengen)

Sein \(\displaystyle S\subset \R^2\) eine endliche Punktmenge.Da die Umkreise von Polygonen mit den Umkreisen ihre Eckpunktmengen übereinstimmen, ist damit auch die Existenz minimaler Umkreise zu Polygonen gesichert.

Beweis

Sei \(\displaystyle \mathcal K\) die Menge aller Umkreise von \(\displaystyle M\). Wir konstruieren eine Abbildung \(\displaystyle \phi: \mathcal K\to\mathcal K\), die jedem Umkreis einen Umkreis mit einem nicht größeren Radius zuordnet und so, dass die Bildmenge \(\displaystyle \phi (\mathcal K)\) endlich ist. Ordne nun \(\displaystyle r:\mathcal K\to\R\) jedem Umkreis seinen Radius zu. Dann gilt: \(\displaystyle r(\phi(k))<=r(K)\) für alle \(\displaystyle K\in\mathcal K\) und da wir für einen beliebigen Umkreis \(\displaystyle K\) immer einen Umkreis aus \(\displaystyle \phi(\mathcal K)\) finden können, dessen Radius nicht größer ist - nämlich \(\displaystyle \phi(K)\) - gilt sogar \(\displaystyle \inf_{K\in\mathcal K} r(\phi(k))=\inf_{K\in\mathcal K} r(k)\) und mit der Endlichkeit von \(\displaystyle \phi (\mathcal K)\), wäre die Existenz gezeigt.
Bleibt die Konstruktion von \(\displaystyle \phi\). Sei \(\displaystyle K\) ein beliebiger Umkreis mit dem Mittelpunkt \(\displaystyle M\). Wir unterscheiden 3 Fälle.
Fall 1: Der Umfang (Rand) von \(\displaystyle K\) enthält keinen Punkt aus \(\displaystyle S\). Wir verkleinern den Radius von \(\displaystyle K\) solange, bis wenigstens ein Punkt auf dem Umfang von \(\displaystyle K\) liegt. Weiter mit Fall 2 , oder 4.
1pu.png
Fall 2
Fall 2: Der Rand von \(\displaystyle K\) enthält genau einen Punkt \(\displaystyle A\) aus \(\displaystyle S\). Wir verschieben den Mittelpunkt \(\displaystyle M_1\) eines neuen Umkreises entlang der Strecke \(\displaystyle \ovl {AM}\) bis der so entstandene Kreis \(\displaystyle K_1\) wenigstens einen weiteren Punkt \(\displaystyle B\in S\) berührt.
Weiter mit Fall 3 oder Fall 4.Fall 3: Der Rand von \(\displaystyle K\) enthält genau 2 Punkte aus \(\displaystyle S\) und seien diese \(\displaystyle A\) und \(\displaystyle B\). Fall 3.1: \(\displaystyle M_K\) liegt auf der Strecke \(\displaystyle \ovl{AB}\), dann setzen wir \(\displaystyle \phi(K)=K\).
2pu.png
Fall 3.2
Fall 3.2: \(\displaystyle M_K\) liegt nicht auf der Strecke \(\displaystyle \ovl{AB}\). Wir verschieben den Mittelpunkt \(\displaystyle M_1\) entlang der Mittelsenkrechte in Richtung \(\displaystyle \ovl {AB}\). Berührt der so entstanden Kreis einen weiteren Punkt, bevor \(\displaystyle M_1\) die Strecke \(\displaystyle \ovl{AB}\) erreicht, so haben wir Fall 4. Erreicht \(\displaystyle M_1\) jedoch die Strecke \(\displaystyle \ovl{AB}\) zuerst, handelt es sich um Fall 3.2. Dann gehen wir wie unter diesen Fällen beschrieben vor.
Fall 4: Der Rand \(\displaystyle K\) enthält wenigstens 3 Punkte aus \(\displaystyle S\), dann ist \(\displaystyle \phi(K)=K\).
Diese Konstruktion ist wohldefiniert und deterministisch, sie liefert für jeden Umkreis einen Umkreis mit kleinerem Radius, der durch eine Teilmenge der Punkte aus \(\displaystyle M\) bestimmt wird. Damit kann es nur endlich viele Bilder für alle möglichen Umkreise geben und wir können die obige Argumentation anwenden. \(\displaystyle \qed\)

Es ist unglaublich, wie unwissend die studirende Jugend auf Universitäten kommt, wenn ich nur 10 Minuten rechne oder geometrisire, so schläft 1/4 derselben sanft ein.

Georg Christoph Lichtenberg

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе