Теорема галереї мистецтв

Теорема галереї мистецтв або музейна проблема — добре вивчена проблема видності в обчислювальній геометрії. Вона походить від реальної задачі охорони художньої галереї за допомогою найменшої можливої кількості камер, що можуть одночасно спостерігати за всією галереєю. В обчислювальній геометрії планування галереї описується за допомогою простого многокутника і кожна камера представлена точкою у многокутнику. Кажуть, що множина точок ${\displaystyle S}$ охороняє многокутник, якщо для кожної точки ${\displaystyle p}$ у многокутнику існує деяка точка ${\displaystyle q\in S}$ така, що відрізок між ${\displaystyle p}$ і ${\displaystyle q}$ не залишає цей многокутник.

Два виміри

Чотири камера покривають цю галерею.

Наявні багато видозмін первісної проблеми, які також згадуються як задачі галереї мистецтв. У деяких версіях камери можна ставити лише уздовж периметра або навіть тільки у вершинах многокутника. Деякі версії вимагають спостереження лише за периметром, або його частиною.

Рішення задачі, в якій камери повинні бути розташовані на вершинах і охоронятися повинні тільки вершини, еквівалентне вирішенню задачі про домінівну множину на графі видимості багатокутника.

Теорема галереї мистецтв Хватала

Названа на честь Вацлава Хватала, задає верхню межу мінімальної кількості камер. Вона стверджує, що ${\displaystyle \left\lfloor n/3\right\rfloor }$ камер завжди достатньо, а іноді необхідно для охорони простого многокутника з ${\displaystyle n}$ вершинами.

Питання про те як багато вершин/хранителів/охоронців необхідно Хваталу поставив Віктор Клі у 1973.^[1] Хватал довів теорема невдовзі по тому.^[2] Доведення Хватала пізніше спростив Стів Фіск, використавши аргумент 3-розфарбування.^[3]

Коротке доведення Фіска

Розфарбування 3 кольорами вершин триангульованого многокутника. Сині вершини утворюють набір з трьох камер, настільки мало як і було гарантовано теоремою галереї мистецтв. Однак, цей набір не оптимальний: цей самий полігон можна охороняти за допомогою двох камер.

Fisk, (1978) довів теорему так.

По-перше, многокутник триангулюють (без додавання додаткових вершин. Тоді вершини многокутника 3-фарбують, так щоб кожний трикутник мав усі три кольори. Для знаходження 3-фарбування корисно звернути увагу на те, що двоїстий граф для триангуляції є деревом, будь-який цикл в двоїстому графі сформує границю дірки в многокутнику, що суперечить припущенню, що многокутник не мав дірок. Це означає, що ми можемо знайти 3-фарбування, використовуючи простий обхід графа як-от пошук у глибину.

Щойно 3-фарбування знайдено, вершини одного кольору утворюють підхожу множину для охорони, оскільки кожне трикутник охороняється його вершиною цього кольору. З того, що три кольори розбивають n вершин многокутника, колір з найменшою кількістю вершин формує правильну множину для охорони з не більше ніж ${\displaystyle \lfloor n/3\rfloor }$ камерами.

Обчислювальна складність

Версія задачі галереї мистецтв як проблема вибору звучить так: маємо многокутник і число k, а треба з'ясувати чи можливо охороняти цей многокутник за допомогою k камер. Ця задача і всі її стандартні варіації (такі як обмеження розташування камер самими вершинами або ребрами многокутника) є NP-складною.^[4]

Однак, існують ефективні алгоритми для множини з не більше ніж ${\displaystyle \lfloor n/3\rfloor }$ камер, що відповідає верхній межі встановленій Хваталом. Таку множину можна знайти за час ${\displaystyle O(n\log n).}$ David Avis and Godfried Toussaint (1981) довів наявність такого алгоритму із використанням техніки розділяй та володарюй. Kooshesh та Moret, (1992) надав алгоритм лінійного часу, використовуючи доведення Фіска і алгоритм триангуляції лінійного часу Бернарда Чазела.

Узагальнення

Існує цілий ряд узагальнень і уточнень оригінальної теореми галереї мистецтв. Наприклад, для ортогональних багатокутників, чиї сторони перетинаються під прямим кутом, необхідно тільки ${\displaystyle \lfloor n/4\rfloor }$ камер. Є принаймні три докази цього результату, жоден з них не простий: Кана, Клейва і Клейтмана; Любіва; Сака і Туссена.

Схожі задачі намагаються визначити, скільки необхідно камер, щоб охопити екстер'єр галереї: ${\displaystyle \lceil n/2\rceil }$ — інколи необхідна і завжди достатня кількість. Іншими словами, нескінченний екстер'єр складніше охороняти, ніж скінченну галерею.

Три виміри

Приклад багатогранника з внутрішніми точками не видними з жодної вершини.

Якщо музей представлено у трьох вимірах як багатогранник, тоді розташування камер у кожній вершині не гарантуватиме, що весь музей під спостереженням. Хоча всі многокутники, що утворюють поверхню спостерігатимуться, все ж залишаться точки, недоступні для камер.^[5]