Orte, an denen die Reihenfolge der Punkte entlang eines einfachen Polygons, das durch sie verläuft, nützlich ist

Wir wissen, dass das Finden der konvexen Hülle von $n$ Punkten in einer Ebene eine Untergrenze von $\Omega(n\log n)$ für die Laufzeit hat. Wenn die Punkte jedoch in der Reihenfolge angegeben werden, in der sie entlang eines einfachen Polygons auftreten, dessen Eckpunkte diese Punkte sind, kann ihre konvexe Hülle in linearer Zeit gefunden werden.

Ich finde das faszinierend, weil es wahrscheinlich zu viele einfache Polygone gibt, die die angegebenen Punkte als Eckpunkte haben, und daher klingt die Reihenfolge entlang eines von ihnen intuitiv wie eine sehr nutzlose Information. Und doch hilft es.

Meine Frage ist also, gibt es andere Stellen, an denen dieselben Informationen dazu beitragen, die Laufzeit eines Algorithmus zu verkürzen?

Nebenbei möchte ich auch die Grenzen der Anzahl der Permutationen einer bestimmten Menge von Punkten in einer Ebene kennen, für die es ein einfaches Polygon mit diesen Punkten als Eckpunkten gibt, so dass die Reihenfolge, in der die Punkte entlang des Polygons auftreten, ist das gleiche wie die Reihenfolge in der Permutation. Was ist darüber bekannt?

$n$$n!$$(n-1)!/2$$2^{\Theta(n \log n)}$

$2^{\Theta(n)}$$<30^n$$<2^{3n-6}$

Die konvexe Hülle einfacher Polygone war eine meiner Lieblingsbeschäftigungen, seit ich sie zum Finden und / oder Formeln von Polygonen in SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472 verwendet habe