Endroits où l'ordre des points le long d'un simple polygone les traversant est utile

Nous savons que trouver la coque convexe de points sur un avion a une limite inférieure de sur son temps de marche. Cependant, si les points sont donnés dans l'ordre dans lequel ils se produisent le long d'un polygone simple qui a ces points comme sommets, leur coque convexe peut être trouvée en temps linéaire.$n$$\Omega(n\log n)$

Je trouve cela intriguant car il y a probablement trop de polygones simples qui ont les points donnés comme sommets et donc, intuitivement, l'ordre le long de l'un d'eux ressemble à une information très inutile. Et pourtant, ça aide.

Ma question est donc la suivante: existe-t-il d'autres endroits où les mêmes informations contribuent à réduire le temps de fonctionnement d'un algorithme?

En tant que côté, je veux également connaître les limites du nombre de permutations d'un ensemble donné de points sur un plan pour lequel il existe un polygone simple avec ces points comme sommets afin que l'ordre dans lequel les points se produisent le long du polygone soit le même que l'ordre dans la permutation. Que sait-on à ce sujet?

Votre commentaire selon lequel "il y a probablement trop de polygones simples" est la clé, car en réalité il n'y en a pas autant. points ontchemins (permutations) et polygones si nous autorisons les auto-intersections - c'est-à-dire .$n$$n!$$(n-1)!/2$$2^{\Theta(n \log n)}$

Le nombre de chemins ou de polygones sans auto-intersections est de , le plus facile à observer du fait que ces chemins et polygones peuvent être complétés en triangulations, le nombre de triangulations d'un point donné défini dans le plan est [Sharir-Sheffer'09, le plus récent d'une longue histoire], et le nombre de sous-ensembles appropriés d'arêtes de chaque triangulation est .$2^{\Theta(n)}$$<30^n$$<2^{3n-6}$

La coque convexe de polygones simples est l'une de mes choses préférées depuis son utilisation pour trouver et / ou des formules de polygones dans SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472