h3. Rubarba

Aceasta problema e clasica in geometria computationala. O prima observatie care ne ajuta in rezolvare este ca numai punctele de pe infasuratoarea convexa influenteaza forma dreptunghiului minim. Deci primul pas in rezolvarea problemei este sa gasim infasuratoarea convexa a punctelor in {$O(N*lg(N))$}. Daca avem fixata o directie atunci e usor sa determinam in $O(h)$ (unde $h$ e numarul de puncte de pe infasuratoarea convexa) cele patru puncte ce marginesc dreptunghiul dupa directia aleasa si dupa directia perpendiculara. Folosind cautare binara pentru a determina cele patru puncte extreme, reducem astfel complexitatea la {$O(lg(h))$}. Observatia finala este ca un dreptunghi de arie minima ce contine o multime de puncte in interior trebuie sa aiba o latura paralela cu una din laturile infasuratorii convexe, aceasta idee este intuitiva dar demonstratia ei nu este foarte simpla. Complexitatea algoritmului ce rezolva problema poate fi $O(N*lg(N) + h^2^)$ sau $O(n*lg(n) + h*lg(h))$ daca folosim cautarea binara. Testele folosite au fost generate aleator, generand aleator puncte in plan infasuratoarea convexa va avea cardinalul $h$ teoretic egal cu {$Theta(lg(N))$}, deci rezolvarea $O(N*lg(N) + h^2^)$ ar fi luat fara probleme punctaj maxim. Mentionam ca exista o tehnica numita "Rotating Calipers" care rezolva aceasta problema si altele similare in {$O(N*lg(N) + h)$}, daca vreti sa cititi despre aceasta tehnica accesati "pagina":http://cgm.cs.mcgill.ca/~orm/rotcal.html. Idei de acolo v-ar fi ajutat sa rezolvati problema propusa recent la ".campion":http://campion.edu.ro/index.php, care cerea separarea a doua poligoane convexe cu o dreapta, si o prolema propusa anul trecut la Bursele Agora care cerea determinarea distantei maxime ce exista intre oricare doua puncte dintr-o multime, si tot pe acea pagina gasiti demonstratia matematica a faptului ca dreptunghiul de arie minima ce contine in interior o multime de puncte are o latura paralela cu o latura a infasuratorii convexe.

Aceasta problema e clasica in geometria computationala. O prima observatie care ne ajuta in rezolvare este ca numai punctele de pe infasuratoarea convexa influenteaza forma dreptunghiului minim. Deci primul pas in rezolvarea problemei este sa gasim infasuratoarea convexa a punctelor in O(N*lg(N)). Daca avem fixata o directie atunci e usor sa determinam in O(h) (unde h e numarul de puncte de pe infasuratoarea convexa) cele patru puncte ce marginesc dreptunghiul dupa directia aleasa si dupa directia perpendiculara. Folosind cautare binara pentru a determina cele patru puncte extreme, reducem astfel complexitatea la O(lg(h)). Observatia finala este ca un dreptunghi de arie minima ce contine o multime de puncte in interior trebuie sa aiba o latura paralela cu una din laturile infasuratorii convexe, aceasta idee este intuitiva dar demonstratia ei nu este foarte simpla. Complexitatea algoritmului ce rezolva problema poate fi O(N*lg(N) + h^2) sau O(n*lg(n) + h*lg(h)) daca folosim cautarea binara. Testele
folosite au fost generate aleator, generand aleator puncte in plan infasuratoarea convexa va avea cardinalul h teoretic egal cu Theta(lg(N)), deci rezolvarea O(N*lg(N) + h^2) ar fi luat fara probleme punctaj maxim. Mentionam ca exista o tehnica numita "Rotating Calipers" care rezolva aceasta problema si altele similare in O(N*lg(N) + h), daca vreti sa cititi despre aceasta tehnica accesati pagina [1]http://cgm.cs.mcgill.ca/~orm/rotcal.html. Idei de acolo v-ar fi ajutat sa rezolvati problema propusa recent la .campion, care cerea separarea a doua poligoane convexe cu o dreapta, si o prolema propusa anul trecut la Bursele Agora care cerea determinarea distantei maxime ce exista intre oricare doua puncte dintr-o multime, si tot pe acea pagina gasiti demonstratia matematica a faptului ca dreptunghiul de arie minima ce contine in interior o multime de puncte are o latura paralela cu o latura a infasuratorii convexe.

h2. Incheiere

Incheiere

Pana la urmatorul concurs, BAFTA LA OJI!

References
 
Visible links
1. http://cgm.cs.mcgill.ca/~orm/rotcal.html