Проблем најкраће непрозирне шуме

У области геометријских алгоритама проблем најкраће непрозирне шуми може да се формулише на следећи начин:"Дат је конвексни полигон Ф. Непрозирна шума је скуп затворених дуж Т са следећим својством: свака права која сече Ф сече и бар једну дуж из скупа Т. Најкраћа непрозирна шума је непрозирна шума таква да је збир дужина дужи које је сачињавају минималан. Проблем најкраће непрозирне шуме је проблем налажења најкраће непрозирне шуме". Ако је Т непрозирна шума полигона Ф кажемо да Т прекрива Ф. Понекад је задат и додатни услов да шума мора бити строго ван или строго унутар полигона.

Непрозирне шуме коцке

Овај проблем први је поставио Мазуркијебич 1916. године. Од тад нису забележени значајнији доприноси решавању овог проблема. Не постоји никакво опште решење овог проблема. Чак ни за једноставније полигоне, као на пример квадрат или једнокостранични троугао, нису позната.

Ограничавање оптималног решења

Могуће је ограничити оптимално решење преко пречника полигона. Нека је пречник датог полигона p. Могуће је доказати да је p/2 ≤ |OPT| ≤ p. , где је |OPT| збир дужина дужи које сачињавају оптималну шуму. Горње ограничење је јасно, јер је пречник полигона свакако непрозирна шума. p/2 ≤ |OPT|- ово ограничење је врло слабо јер се гранични случај достиже само за полигоне јако мале површине а релативно великог пречника(нпр. једнакокраки троугао чији су краци много дужи од основе има најкраћу непрозирну шуму дужине приближно једнаке свом полупречнику. Штавише, повећавањем односа дужина кракова и основе једнакокраког троугла дужина његове најкраће непрозирне шуме може да буде произвољно близу његовом полупречнику). За случај квадрата доказано је да је дужина најкраће разапињуће шуме бар 2 + 10⁻¹².

Провера прекривености

Шума Т не прекрива конвексне полигоне који нису у целости садржани у унутрашњости конвексног омотача од Т. Ово важи јер ако претпоставимо да Т покрива ф, а Ф није садржан у конвексном омотачу од Т онда постоји тачка А ван конвексног омотача од Т а унутар Ф и кроз ту тачку можемо провући праву која не садржи конвексни омотач од Т(кроз сваку тачку ван конвексне фигуре може се провући права таква да ту конвексну фигуру не сече), па самим ти не сече ни једну дуж унутар T. Контрадикција. Међутим, да би Т прекривало конвексну фигуру Ф није довољно да Ф припада конвексном омотачу шуме Т. Једино ако је Т стабло можемо са сигурношћу рећи да Т покрива свој конвексни омотач, па самим тим и сваку конвексну фигуру унутар тог конвексног омотача.

Област прекривености

Јасно је да ако шума Т прекрива конвексне полигоне Ф и П онда Т прекрива и њихову унију. Унија свих конвексних полигона које T прекрива назива се област прекривености шуме Т. Поставља се питање која је област прекривености проивољне шуме Т. Посматрајмо конвексне омотаче дрва која сачињавају шуму Т. Конструсаћемо скупове тачака А_п за сваку тачку п на рубу сваког од ових конвексних омотача. Унија свих правих које пролаѕе кроз п и секу неки од конвексних омотача дрвећа шуме Т назовимо А_п. Пресек скупова А_п свих тачака која су темена свих конвексних омотача дрвећа шуме Т представља област прекривености шуме Т. Из конструкције области прекривености види се да би проблем налажења ове области могуће решити у Θ(m²n²). Овај алгоритам је у најгорем случају оптималан, међутим за многе случајеве овај алгоритам ради пуно беспотребног рачунања, јер се многи конвексни омотачи преклапају. Ако се два конвексна омотача преклапају могу бити замењени са конвексним омотачем свих тачака та два стабла. Ако након спајања свих преклапајућих конвексних омотача добијемо једну фигуру онда је баш та фигура област прекривености шуме Т. Овај специјалан случај има O(nlog²n) временску сложеност. Ако након спајања преклопљених конвексних омотача стабала имамо више фигура можемо само применити горе споменути алгоритам с тим што уместо сваког конвексног омотача појединачно посматрамо ове нове фигуре настале спајањем преклопљених конвексних омотача.