Problem najkraće neprozirne šume

U oblasti geometrijskih algoritama problem najkraće neprozirne šumi može da se formuliše na sledeći način:"Dat je konveksni poligon F. Neprozirna šuma je skup zatvorenih duž T sa sledećim svojstvom: svaka prava koja seče F seče i bar jednu duž iz skupa T. Najkraća neprozirna šuma je neprozirna šuma takva da je zbir dužina duži koje je sačinjavaju minimalan. Problem najkraće neprozirne šume je problem nalaženja najkraće neprozirne šume". Ako je T neprozirna šuma poligona F kažemo da T prekriva F. Ponekad je zadat i dodatni uslov da šuma mora biti strogo van ili strogo unutar poligona.

Neprozirne šume kocke

Ovaj problem prvi je postavio Mazurkijebič 1916. godine. Od tad nisu zabeleženi značajniji doprinosi rešavanju ovog problema. Ne postoji nikakvo opšte rešenje ovog problema. Čak ni za jednostavnije poligone, kao na primer kvadrat ili jednokostranični trougao, nisu poznata.

Ograničavanje optimalnog rešenja

Moguće je ograničiti optimalno rešenje preko prečnika poligona. Neka je prečnik datog poligona p. Moguće je dokazati da je p/2 ≤ |OPT| ≤ p. , gde je |OPT| zbir dužina duži koje sačinjavaju optimalnu šumu. Gornje ograničenje je jasno, jer je prečnik poligona svakako neprozirna šuma. p/2 ≤ |OPT|- ovo ograničenje je vrlo slabo jer se granični slučaj dostiže samo za poligone jako male površine a relativno velikog prečnika(npr. jednakokraki trougao čiji su kraci mnogo duži od osnove ima najkraću neprozirnu šumu dužine približno jednake svom poluprečniku. Štaviše, povećavanjem odnosa dužina krakova i osnove jednakokrakog trougla dužina njegove najkraće neprozirne šume može da bude proizvoljno blizu njegovom poluprečniku). Za slučaj kvadrata dokazano je da je dužina najkraće razapinjuće šume bar 2 + 10⁻¹².

Provera prekrivenosti

Šuma T ne prekriva konveksne poligone koji nisu u celosti sadržani u unutrašnjosti konveksnog omotača od T. Ovo važi jer ako pretpostavimo da T pokriva f, a F nije sadržan u konveksnom omotaču od T onda postoji tačka A van konveksnog omotača od T a unutar F i kroz tu tačku možemo provući pravu koja ne sadrži konveksni omotač od T(kroz svaku tačku van konveksne figure može se provući prava takva da tu konveksnu figuru ne seče), pa samim ti ne seče ni jednu duž unutar T. Kontradikcija. Međutim, da bi T prekrivalo konveksnu figuru F nije dovoljno da F pripada konveksnom omotaču šume T. Jedino ako je T stablo možemo sa sigurnošću reći da T pokriva svoj konveksni omotač, pa samim tim i svaku konveksnu figuru unutar tog konveksnog omotača.

Oblast prekrivenosti

Jasno je da ako šuma T prekriva konveksne poligone F i P onda T prekriva i njihovu uniju. Unija svih konveksnih poligona koje T prekriva naziva se oblast prekrivenosti šume T. Postavlja se pitanje koja je oblast prekrivenosti proivoljne šume T. Posmatrajmo konveksne omotače drva koja sačinjavaju šumu T. Konstrusaćemo skupove tačaka A_p za svaku tačku p na rubu svakog od ovih konveksnih omotača. Unija svih pravih koje prolaѕe kroz p i seku neki od konveksnih omotača drveća šume T nazovimo A_p. Presek skupova A_p svih tačaka koja su temena svih konveksnih omotača drveća šume T predstavlja oblast prekrivenosti šume T. Iz konstrukcije oblasti prekrivenosti vidi se da bi problem nalaženja ove oblasti moguće rešiti u Θ(m²n²). Ovaj algoritam je u najgorem slučaju optimalan, međutim za mnoge slučajeve ovaj algoritam radi puno bespotrebnog računanja, jer se mnogi konveksni omotači preklapaju. Ako se dva konveksna omotača preklapaju mogu biti zamenjeni sa konveksnim omotačem svih tačaka ta dva stabla. Ako nakon spajanja svih preklapajućih konveksnih omotača dobijemo jednu figuru onda je baš ta figura oblast prekrivenosti šume T. Ovaj specijalan slučaj ima O(nlog²n) vremensku složenost. Ako nakon spajanja preklopljenih konveksnih omotača stabala imamo više figura možemo samo primeniti gore spomenuti algoritam s tim što umesto svakog konveksnog omotača pojedinačno posmatramo ove nove figure nastale spajanjem preklopljenih konveksnih omotača.