Die Anzahl der Triangulationen einer Menge von

Nachdem ich Emo Welzl diesen Sommer zu diesem Thema sprechen hörte, weiß ich, dass die Anzahl der Triangulationen einer Menge von Punkten in der Ebene irgendwo zwischen und . Entschuldigung, wenn ich veraltet bin; Updates erwünscht. $n$ $\Omega(8.48^n)$ $O(30^n)$

Ich erwähnte dies in der Klasse und wollte den Schülern eine kurze, weise Bemerkung geben, um zu verstehen, (a) warum es sich als so schwierig erwiesen hat, diese Menge festzunageln, und (b) warum es so vielen wichtig ist , sie festzunageln. Ich stellte fest, dass ich keine angemessenen Antworten hatte, um eines der beiden Themen zu beleuchten. so viel zu meinem sageness!

Ich würde mich freuen, wenn Sie diese zugegebenermaßen vagen Fragen beantworten. Vielen Dank!

co.combinatorics cg.comp-geom Joseph O'Rourke
quelle

Laut der Polygonisierungsseite von Erik Demaine lautete die im Vortrag angegebene Grenze

, aber ich kann mich nicht erinnern, ob Emo Welzl angegeben hat, dass man mit einer genaueren Analyse eine bessere Grenze nachweisen könnte. Aus irgendeinem Grund habe ich

im Kopf.

O (56^{n})

$O(56^n)$

O (35^{n})

$O(35^n)$

Timothy Sun

Auf derselben Seite steht "Die derzeit beste Grenze ist 30". Die Zahl 56 steht für die Polygonisierung.

Chao Xu

Vielleicht lohnt es sich, meine Fragen selbst zu beantworten. Triangulationen werden durch nicht kreuzende Segmente gebildet. Noncrossing-Ness zu verstehen ist schwierig. Das ist ein). Für (b) wird das Streben durch den Versuch getrieben, Nichtkreuzungen zu verstehen. Ich denke, Sie werden mir zustimmen, dass diese Antworten unzureichend sind.

Joseph O'Rourke

Als Referenz ist das gleiche für Punkte in konvexer Position eine Hausaufgabe über katalanische Zahlen. Dies liegt daran, dass wir die Nicht-Kreuzung auf eine schöne Art und Weise durch ausgeglichene Klammern charakterisieren können (Punkt (a)

glaubwürdig machen

Ich möchte sagen, dass dieses Problem nicht direkt mit dem EDC zusammenhängt. Hauptsächlich, weil ein Schlüsselproblem darin besteht, nicht kreuzende Paare zu charakterisieren, und weil diese Frage einen viel stärkeren topologischen als geometrischen Charakter hat (und wir haben Indizien dafür, dass der EDC von Natur aus geometrisch ist)

Suresh Venkat,

Die Anzahl der Triangulationen einer Menge von

Antworten: