Miejsca, w których przydatna jest kolejność punktów wzdłuż przechodzącego przez nie prostokąta

Wiemy, że znalezienie wypukłego kadłuba punktów na płaszczyźnie ma dolną granicę w czasie jego działania. Jeśli jednak punkty są podane w kolejności, w jakiej występują wzdłuż prostego wielokąta, który ma te punkty jako wierzchołki, to ich wypukły kadłub można znaleźć w czasie liniowym.$n$$\Omega(n\log n)$

Uważam to za intrygujące, ponieważ prawdopodobnie istnieje zbyt wiele prostych wielokątów, które mają podane punkty jako wierzchołki, a zatem intuicyjnie kolejność wzdłuż jednego z nich brzmi jak bardzo bezużyteczna informacja. A jednak pomaga.

Moje pytanie brzmi: czy są inne miejsca, w których te same informacje pomagają skrócić czas działania algorytmu?

Z boku chcę również poznać granice liczby permutacji danego zestawu punktów na płaszczyźnie, dla której istnieje prosty wielokąt z tymi punktami jako wierzchołkami, tak aby kolejność występowania punktów wzdłuż wielokąta wynosiła taka sama jak kolejność w permutacji. Co o tym wiadomo?

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

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

Wypukły kadłub prostych wielokątów jest jedną z moich ulubionych rzeczy, odkąd używam go do wyszukiwania i / lub formuł wieloboków w SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472