Сурет галереясы мәселесі: геометриялық және қолданбалы аспектілер

Кіріспе

Математикалық мәселе

Көркемсурет галереясы немесе музей мәселесі – есептеу геометриясындағы жақсы зерттелген көріну проблемасы. Бұл мәселе мынандай нақты жағдайдан туындайды:

"Көркемсурет галереясында, галереяның барлық бөлігін қадағалай алатын ең аз қанша күзетші керек?" Мәселенің геометриялық түрінде галереяның орналасуы қарапайым көпбұрышпен көрсетіледі, ал әрбір күзетші көпбұрыш ішіндегі нүктемен бейнеленеді. Нүктелер жиыны, егер көпбұрыштың кез келген нүктесі үшін, сол нүкте мен жиындағы кез келген нүкте арасындағы түзу сызығы сегменті көпбұрыштан шықпаса, онда көпбұрышты қадағалайды деп айтылады. Көркемсурет галереясы мәселесі робототехника сияқты салаларда қолданылуы мүмкін, мысалы, жасанды интеллект (ЖИ) өз қоршаған ортасына байланысты қозғалыстарды орындауы керек болғанда. Бұл мәселені қолданатын басқа да салалар – кескіндерді өңдеу, сахнаны жарықтандыру мәселелері немесе табиғи апаттар туралы ескерту үшін инфрақұрылым құру.

Екі өлшемді

Бастапқы мәселенің көптеген нұсқалары бар, олар сонымен қатар өнер галереясы мәселесі деп аталады. Кейбір нұсқаларда күзетшілер периметрмен немесе тіпті көпбұрыштың төбелерімен шектеледі. Кейбір нұсқаларда тек периметрді немесе периметрдің бір бөлігін күзету талап етіледі. Күзетшілерді төбелерге орналастыру қажет және тек төбелерді қорғау жеткілікті болатын нұсқаны шешу, көпбұрыштың көріну графигіндегі үстемдік жиынтығы мәселесін шешумен эквивалентті.

Шваталдың өнер галереясы теоремасы

Шваталдың Václav Chvátal атындағы өнер галереясы теоремасы күзетшілердің ең аз санын жоғары шекте анықтайды. Онда былай делінеді: "Төбелері бар қарапайым көпбұрышты күзету үшін күзетшілер әрқашан жеткілікті және кейде қажет".

Тарих

1973 жылы Виктор Кли Хваталға қанша төбе / күзетші / сақшы қажет екені туралы сұрақ қойылды. Хватал оны көп ұзамай дәлелдеді. Хваталдың дәлелін кейін Стив Фиск 3 түстің көмегімен қарапайымдастырды. Хватал көбірек геометриялық тәсіл қолданады, ал Фиск граф теориясынан белгілі нәтижелерді пайдаланады.

Дәлелдің көрінісі

Дәлелді көрсету үшін төмендегі көпбұрышты қарастырайық. Бірінші қадам – көпбұрышты үшбұрыштарға бөлу (1-суретті қараңыз). Содан кейін, дұрыс түспен бояу қолданылады (2-сурет) және қызыл, көк және жасыл түсті төбелердің бар екені байқалады. Ең аз санында төбесі бар түс көк немесе қызыл, сондықтан көпбұрыш күзетшілермен жабылуы мүмкін (3-сурет). Бұл галерея теоремасымен сәйкес келеді, өйткені көпбұрышта төбелер бар, және .

Жалпылау

Шваталдың жоғарғы шегі, егер бұрыштардағы күзетшілерге қойылған шектеу полигоннан тыс жердегі кез келген нүктедегі күзетшілерге жеңілдетілсе, күшінде қалады. Бастапқы өнер галереясы теоремасының көптеген басқа да жалпыламалары мен ерекше жағдайлары бар. Мысалы, тік бұрыштарда жиектері/қабырғалары кездесетін ортогональды көпбұрыштар үшін тек күзетшілер қажет. Бұл нәтижеге кем дегенде үш анық дәлел бар, олардың ешқайсысы да оңай емес: Кан, Клау және Клейтман; Любив; және Сак пен Туссен. Бұған байланысты мәселе кез келген көпбұрыштың сыртын күзетуге қажетті күзетшілердің санын анықтау болып табылады ("Бекініс мәселесі"): егер күзетшілер көпбұрыш шекарасына орналасса, кейде қажет және әрқашан жеткілікті, ал егер күзетшілер көпбұрыш сыртының кез келген жеріне орналасса, кейде қажет және әрқашан жеткілікті. Басқаша айтқанда, шексіз сыртқы жағын жабу, шекті ішкі жағын жабудан қиын.

Есептеу күрделілігі

Көркемсурет галереясы мәселесінің шешімдік нұсқаларында, кіріс ретінде көпбұрыш пен k саны беріледі және көпбұрышты k немесе одан кем күзетшілермен күзетуге болатынын анықтау керек. Бұл мәселе толық, сақшылар көпбұрыш қабырғаларымен шектелген жағдайда да. Сонымен қатар, көптеген басқа стандартты өзгерістер (мысалы, күзетшілердің орналасқан жерін төбелермен шектеу) NP-қиын. Күзетшілердің ең аз санына жуықтау алгоритмдері үшін, мәселе APX-қиын екені дәлелденді, яғни полиномиалдық уақыттағы жуықтау алгоритмі белгілі бір тұрақтыдан жақсы нәтиже бере алмайды. Ең аз төбелік күзетшілер саны үшін логарифмдік жуықтауға қол жеткізуге болады, көпбұрышты дөңгелекшеге бөліп, содан кейін мәселені жиынтық жабу мәселесіне келтіру арқылы. Көрсетілгендей, көркемсурет галереясы мәселесінен туындаған жиын жүйесінің VC өлшемі шектеулі, бұл ε-торларға негізделген жиынтық жабу алгоритмдерін қолдануға мүмкіндік береді, олардың жуықтау қатынасы оңтайлы күзетшілер санының логарифміне, көпбұрыш төбелерінің санына қарағанда жақын. Күзетшілердің орналасқан жері шектелмеген жағдайда, проблема одан да қиын. Алайда, күзетшілерді тығыз торға орналастыру арқылы, кейбір қосымша шарттар орындалса, күрделі логарифмдік жуықтау алгоритмін құруға болады. Тиімді алгоритмдер ең көп дегенде n төбелік күзетшілер жиынын табуға белгілі, бұл Chvátal-дың жоғарғы шегімен сәйкес келеді. Бұл күзетшілердің орналасуын ең жаман жағдайда O(n log n) уақытында бөліп-басқару алгоритмі арқылы есептеуге болады. Fisk-тің қысқа дәлелін және Bernard Chazelle-дің жазықтық үшбұрыштау алгоритмін пайдалану арқылы сызықтық уақыт алгоритмі ұсынылды. Төбелері жоқ қарапайым көпбұрыштар үшін, төбелік және қабырғалық күзетшілер үшін тұрақты факторлы жуықтау алгоритмінің бар екендігі Ghosh болжады. Ghosh-тың болжамы алдымен қарапайым көпбұрыштардың екі арнайы кіші класындағы төбелік күзетшілер үшін дұрыс екені дәлелденді, атап айтқанда, монотонды көпбұрыштар және қабырғасынан нашар көрінетін көпбұрыштар. Монотонды көпбұрыш үшін төбелік күзетшілер жиынын полиномиалдық уақытта есептейтін жуықтау алгоритмі ұсынылды, мұнда күзетшілер жиынының мөлшері оңтайлы төбелік күзетшілер санынан 30 есе артық емес. Қабырғасынан нашар көрінетін қарапайым көпбұрыш үшін O(n^2) уақытында төбелік күзетшілер жиынын есептейтін жуықтау алгоритмі ұсынылды, мұнда күзетшілер жиынының мөлшері оңтайлы төбелік күзетшілер санынан 6 есе артық емес. Кейіннен, тұрақты факторлы жуықтау алгоритмдерін ұсыну арқылы жалпы қарапайым көпбұрыштарды күзету үшін болжамды толық шешкенін мәлімдеді. Қабырғасынан нашар көрінетін қарапайым көпбұрыштардың кіші класын күзету үшін полиномиалдық уақытқа жуықтау схемасы ұсынылды. Авторлар бірнеше кластағы көпбұрыштармен кең ауқымды есептеу эксперименттерін жүргізді, бұл оңтайлы шешімдерді салыстырмалы түрде аз есептеу уақытында, тіпті мыңдаған төбелері бар инстанциялар үшін де табуға болатынын көрсетті. Кіріс деректері мен осы инстанцияларға арналған оңтайлы шешімдер жүктеуге қол жетімді.

In decision problem versions of the art gallery problem, one is given as input both a polygon and a number k, and must determine whether the polygon can be guarded with k or fewer guards. This problem is complete, as is the version where the guards are restricted to the edges of the polygon. Furthermore, most of the other standard variations (such as restricting the guard locations to vertices) are NP hard. Regarding approximation algorithms for the minimum number of guards, proved the problem to be APX hard, implying that it is unlikely that any approximation ratio better than some fixed constant can be achieved by a polynomial time approximation algorithm. showed that a logarithmic approximation may be achieved for the minimum number of vertex guards by discretizing the input polygon into convex subregions and then reducing the problem to a set cover problem. As showed, the set system derived from an art gallery problem has bounded VC dimension, allowing the application of set cover algorithms based on ε nets whose approximation ratio is the logarithm of the optimal number of guards rather than of the number of polygon vertices. For unrestricted guards, the infinite number of potential guard positions makes the problem even more difficult. However by restricting the guards to lie on a fine grid, a more complicated logarithmic approximation algorithm can be derived under some mild extra assumptions, as shown by However, efficient algorithms are known for finding a set of at most vertex guards, matching Chvátal's upper bound. proved that a placement for these guards may be computed in O(n log n) time in the worst case, via a divide and conquer algorithm. gave a linear time algorithm by using Fisk's short proof and Bernard Chazelle's linear time plane triangulation algorithm. For simple polygons that do not contain holes, the existence of a constant factor approximation algorithm for vertex and edge guards was conjectured by Ghosh. Ghosh's conjecture was initially shown to be true for vertex guards in two special sub classes of simple polygons, viz. monotone polygons and polygons weakly visible from an edge. presented an approximation algorithm that computes in polynomial time a vertex guard set for a monotone polygon such that the size of the guard set is at most 30 times the optimal number of vertex guards. presented an approximation algorithm that computes in O(n2) time a vertex guard set for a simple polygon that is weakly visible from an edge such that the size of the guard set is at most 6 times the optimal number of vertex guards. Subsequently, claimed to have settled the conjecture completely by presenting constant factor approximation algorithms for guarding general simple polygons using vertex guards and edge guards. For vertex guarding the subclass of simple polygons that are weakly visible from an edge, a polynomial time approximation scheme was proposed by
An exact algorithm was proposed by for vertex guards. The authors conducted extensive computational experiments with several classes of polygons showing that optimal solutions can be found in relatively small computation times even for instances associated to thousands of vertices. The input data and the optimal solutions for these instances are available for download.

Үш өлшемді

Егер мұражай үш өлшемді көпжақ түрінде бейнеленсе, онда әрбір төбесіне күзетші қою мұражайдың барлық бөлігінің қадағалануын қамтамасыз етпейді. Көпжақтың барлық беті қарастырылса да, кейбір көпжақтардың ішінде қадағалаудан тыс қалған нүктелер болуы мүмкін.