Kreis durch Auswahl von Punkten am Umfang in Stücke aufteilen?

Question

Auf einem Kreis, N beliebige Punkte sind auf seinem Umfang gewählt. Der vollständige Graph, der mit diesen N Punkten gebildet wurde, würde den Bereich des Kreises in viele Teile teilen.

Wie groß ist die maximale Anzahl von Flächenstücken, in die der Kreis geteilt wird, wenn die Punkte entlang seines Umfangs ausgewählt werden?

Beispiele:

• 2 Punkte => 2 Stück
• 4 Punkte => 8 Stück

Irgendwelche Ideen, wie um dies zu realisieren?

Answer 1

Dies ist bekannt als Moser's circle problem.

Die Lösung lautet:

heißt

Der Beweis ist ganz einfach:

jeder Kreuzung innerhalb des Kreises in Betracht. Es muss durch den Schnittpunkt zweier Linien definiert werden, und jede Linie hat zwei Punkte, so dass jeder Schnittpunkt innerhalb des Kreises 4 eindeutige Punktsätze auf dem Umfang definiert. Daher gibt es höchstens n choose 4 innere Eckpunkte, und offensichtlich gibt es n Eckpunkte auf dem Umfang.

Nun, wie viele Kanten berührt jeder Scheitelpunkt? Nun, es ist ein kompletter Graph, also berührt jeder Eckpunkt auf der Außenseite n - 1 Kanten und natürlich berührt jeder Eckpunkt auf der Innenseite 4 Kanten. Also ist die Anzahl der Kanten gegeben durch (n(n - 1) + 4(n choose 4))/2 (wir dividieren durch zwei, weil sonst jede Kante zweimal durch ihre zwei Ecken gezählt würde).

Der letzte Schritt besteht darin, die Euler-Formel für die Anzahl der Flächen in einem Graphen zu verwenden, d. H .: v - e + f = 1 (die Euler characteristic ist in unserem Fall 1).

Auflösen nach f gibt die Formeln oben :-)