O observatie matematica care ajuta la optimizarea acestui algoritm este faptul ca in functie de un punct din interiorul poligonului, varfurile par sa fie sortate in functie de unghi, si astfel cautarea unui punct care trebuie scos se reduce la o cautare binara de complexitate $O(Nlog{~2~}H)$. Secventa de puncte care trebuie scoase sunt un interval compact mereu si astfel dupa ce se gaseste primul punct se pot determina toate punctele care trebuie scoase in o singura parcurgere a lor. Dar acum mai trebuie o structura de date care permite stergere,inserare si cautare in $O(log~2~N)$. O astfel de structura de date este "Arborele Echilibrati de cautare":http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree, dar care spre norocul nostru sunt implementati deja in stl sub forma de "set-uri":http://www.sgi.com/tech/stl/set.html. O astfel de solutie are complexitate $O(Nlog{~2~}N)$.
Mai trebuie mentionat ca cea mai buna complexitate practica descoperita pana la momentul scrierii acestui articol este $O(Nlog{~2~}H)$, dar si aceasta complexitate teoretic este $O(Nlog{~2~}N)$.

h3. Aplicati

h3. Aplicatii

* Distanta maxima intre $2$ puncte.
* "forum":http://campion.edu.ro/problems/3/468/forum_ro.htm