|
Das Geradlinige Überkreuzende Zahlen Projekt
Viele Fragen in der Berechnungs- und
kombinatorischen Geometrie basieren auf begrenzten Sätzen Punkten in
der euklidischen Fläche. Einige Probleme von der Graphentheorie
auch gepaßt in diesen Rahmen, wenn Ränder eingeschränkt werden, um
gerade zu sein.
Eine typische Frage ist das vorstehende Problem
der geradlinigen Überkreuzenden Zahl (bezogen auf Transportproblemen und
Optimierung der Druckpläne zum Beispiel): Was ist die kleinste Überkreuzende Zahl einer Linealzeichnung des vollständigen Graphen auf
einen Satz n Punkte in der Fläche erreicht? Hier bedeutet
vollständiger Graph, daß irgendein Paar Punkte durch ein Lineal
angeschlossen wird. Außerdem nehmen wir allgemeine Position
für die Punkte an, d.h. liegen keine drei Punkte auf einer
allgemeinen Linie.
Es ist nicht schwer, zu sehen, daß wir vier Punkte in eine Linie legen können, damit keine Überschneidung auftritt. Für fünf
Punkte zeigt die Zeichnung unterschiedliche Weisen, sie zu setzen
(diese sind alle die unterschiedlichen(eingeführt durch Goodman und Pollacks 1983)).
Wenn Sie fünf Punkte in konvexe Positionen dann legen, gibt es
fünf Überfahrten. Das beste, das Sie tun können, ist, nur
kreuzendes ein zu erhalten (es gibt keine Weise, einen vollständigen
Graphen in fünf Punkten ohne Überfahrten zu zeichnen, selbst wenn
Sie die Ränder Kurven sein lassen). BTW: Die Anzahl
der Überschneidungen zu maximieren ist einfach: Gerechter Platz alle n
Punkte auf einem Kreis, zum des Maximums von n zu erhalten wählen 4
Überfahrten.
Für größere Punktsätze ist es sehr hart, die beste
Konfiguration festzustellen. Der Hauptgrund ist, daß die Zahl
kombinatorisch unterschiedlichen Weisen, jene Punkte zu setzen
exponential wächst. Z.B. bereits für n=11 gibt es
2.334.512.907 unterschiedliche Konfigurationen.
Die bemerkenswerte Jagd für Überfahrtzahlen des
vollständigen Graphen ist von R. Guy in den sechziger Jahren
eingeleitet worden. Bis die Werte des Jahres 2000 nur für n<=9 have been found, in 2001 n=10 was solved and the case n=11
was settled in 2004. Von den
sehr neuen (nicht sogar schon veröffentlicht) mathematischen
Betrachtungen bekannt die geradlinigen Überfahrtzahlen für n=19 und
n=21 auch. So ist tantalizing Problem jetzt, den zutreffenden
Wert für n=18 festzustellen, das der Hauptfokus dieses Projektes ist.
|
