Lugares donde es útil el orden de los puntos a lo largo de un polígono simple que los atraviesa

Sabemos que encontrar el casco convexo de $n$ puntos en un plano tiene un límite inferior de $\Omega(n\log n)$ en su tiempo de ejecución. Sin embargo, si los puntos se dan en el orden en que ocurren a lo largo de un polígono simple que tiene esos puntos como vértices, entonces su casco convexo se puede encontrar en tiempo lineal.

Esto me parece intrigante porque probablemente hay demasiados polígonos simples que tienen los puntos dados como vértices y, por lo tanto, intuitivamente, el orden a lo largo de uno de ellos suena como una información muy inútil. Y sin embargo, ayuda.

Entonces mi pregunta es, ¿hay otros lugares donde la misma información ayuda a reducir el tiempo de ejecución de un algoritmo?

Como lado, también quiero conocer los límites en el número de permutaciones de un conjunto dado de puntos en un plano para el que hay un polígono simple con esos puntos como sus vértices, de modo que el orden en que ocurren los puntos a lo largo del polígono es lo mismo que el orden en la permutación. ¿Qué se sabe sobre esto?

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

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

El casco convexo de polígonos simples ha sido una de mis cosas favoritas desde que lo usé para encontrar y / o fórmulas para polígonos en SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472