Задача про густий ліс
В обчислювальній геометрії, проблема густого лісу може бути сформульована таким чином: «Для опуклого багатокутника С в площині, визначити мінімальний ліс Т замкнених, обмежених відрізків, таких, що кожна лінія, яка проходить через C, також перетинає Т». Т називається густим лісом, або бар'єром для C. Відповідно C називається охопленням T. Задача в тому, щоб серед усіх лісів, які охоплюють С (є бар'єром для C), знайти ліс з найменшою довжиною.
У випадку коли Т розташований тільки у внутрішній або тільки у зовнішній частині C, тоді бар'єр називається, відповідно, внутрішнім або зовнішнім. В інших випадках, вважається, що на бар'єр не накладається жодних обмежень.
Історія і труднощі[ред. | ред. код]
Проблема густого лісу вперше розглядалась Стефаном Мазуркевичем[en] в 1916 році.[1] Відтоді не було суттєвого просування щодо початкової проблеми. Не існує будь-яких способів перевірити загальне розв'язання цієї проблеми. Насправді, оптимальне розв'язання навіть для простих фіксованих входових даних, таких як одиничний квадрат або рівносторонній трикутник, невідоме. Існують гіпотетичні оптимальні рішення для обох цих випадків, але на даний час відсутні інструменти для доведення їх оптимальності.[2] Хоча загальні вирішення проблеми були заявлені декількома особами,[3][4] вони або не були розглянуті експертами, або була показана їх помилковість.[5][6]
Обмеження оптимального рішення[ред. | ред. код]
Для заданого опуклого многокутника C з периметром p, можна оцінити значення оптимального рішення через p. Ці оцінки є точними в кожному конкретному випадку, але через те, що фігури можуть набувати різних форм, які взагалі можуть бути, то ці оцінки слабо пов'язані між собою.
У загальному випадку можна довести, що p/2 ≤ |OPT| ≤ p.
Верхня межа[ред. | ред. код]
Зрозуміло, що повторення периметру С достатньо для покриття. Тому p є верхньою межею для будь-якого C. Для внутрішніх бар'єрів ця межа точна в граничному випадку, коли C — коло. Тому, що кожна точка q на колі повинна міститися в T, бо, інакше, дотична до C може бути проведена через q без перетину T. Однак для будь-якого іншого опуклого багатокутника це є неоптимальним, що означає, що це не найліпша верхня межа для багатьох фігур.
Для більшості вхідних даних трохи краща верхня межа для опуклих багатокутників може бути отримана як довжина периметра, за винятком найдовшого ребра (що фактично є мінімальним кістяковим деревом). Більш того, можна взяти мінімальне дерево Штейнера вершин багатокутника. Для внутрішніх бар'єрів єдиним способом поліпшити цю межу є створення незв'язаного бар'єра.
Нижня межа[ред. | ред. код]
Різні докази нижньої межі можна знайти в Dumitrescu та Jiang, (2014). Щоб переконатися, що ці оцінки є точними в загальному випадку, можна розглянути випадок розтягування дуже довгого і тонкого прямокутника. Будь-який густий ліс для цієї форми повинен бути принаймні таким же довгим, як прямокутник, або ж є отвір, через яке можуть проходити вертикальні лінії. Відповідно до того, як прямокутник стає довшим і тоншим, це значення наближається до p/2. Тому ця оцінка в загальному випадку точна. Однак для будь-якої фігури з не нульовою площею, потрібна додаткова довжина, щоб охопити фігуру в інших напрямках. Отже, це не особливо гарна нижня межа для більшості входових даних.
Особливі випадки[ред. | ред. код]
Для одиничного квадрата, ці оцінки — 2 і 4 відповідно. Проте, ці оцінки були дещо поліпшено: нижні межі 2 + 10−12 для бар'єрів, які задовольняють обмеження локальності і 2 + 10−5 для внутрішніх бар'єрів.[7]
Наближення[ред. | ред. код]
Через труднощі, з якими довелося зіткнутися, щоб знайти оптимальний бар'єр для навіть простих прикладів, стало дуже бажано знайти бар'єр, який є наближенням до оптимального з деяким сталим множником.
Думітреску та інші[2] надають кілька лінійних наближень для оптимального рішення. Для загальних бар'єрів вони забезпечують коефіцієнт наближення 1/2 + (2 + √2)/π = 1.5867.... Для пов'язаних бар'єрів вони покращують це співвідношення до 1,5716. Якщо бар'єр обмежений однією дугою, він досягає відношення (π + 5)/(π + 2) = 1.5834.
Перевірка бар'єрів і обчислення охоплення лісів[ред. | ред. код]
Більшість бар'єрних конструкцій такі, що факт покриття необхідниої ділянки, гарантований. Однак, з огляду на довільний бар'єр T, було б бажано підтвердити, що він охоплює бажану область C.
Для простої першої перевірки можна порівняти опуклі оболонки C і T. T охоплює не більше ніж свою опуклу оболонку, тому якщо опукла оболонка T не містить строго C, то вона не може покрити T. Це дає простий O (N log n) алгоритм першої перевірки бар'єру. Якщо T складається з однієї компоненти зв'язності, то він покриває точно її опуклу оболонку, і цей алгоритм є достатнім. Однак, якщо T містить більше однієї компоненти, він може покривати менше. Таким чином, цей тест в цілому недостатній.
Проблема визначення того, які саме області покриває будь-який даний ліс T, що складається з m компонент зв'язності та n ділянок лінії, може бути вирішена за час Θ(m2n2).[8] Основна процедура для цього проста: спочатку спростити кожну компоненту зв'язності, замінивши її своєю опуклою оболонкою. Потім для вершини p кожної опуклої оболонки виконайти кругову розгортку по площині з центром в точці p, відстежуючи, коли ця лінія не проколює опуклу оболонку (крім самої точки p). Орієнтації лінії замітання, під час чого шукається перетин, створюють «сонце»-подібну множина точок (набір клинців з центром в точці р). Покриття T в точності є перетином всіх цих «сонець» для всіх точок p.
Хоча цей алгоритм оптимальний в найгіршому випадку, він часто робить багато непотрібної роботи. Зокрема, коли опуклі оболонки спочатку обчислюються, багато з них можуть перекриватися. Якщо це так, то їх можна замінити на їх об'єднану опуклу оболонку без втрати загальності. Якщо після злиття всіх оболонок, що перекриваються, виник єдиний бар'єр, тоді більш загальний алгоритм не потрібно виконувати; покриття бар'єру не перевищує його опуклу оболонку, і, як ми щойно визначили, його покриття — це його опукла оболонка. Об'єднані оболонки можуть бути обчислені за час O(nlog2n). Якщо залишилося кілька оболонок, алгоритм може бути виконаний на новому спрощеному наборі оболонок і тим самим час обчислення буде зменшено.[9]
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ S. Mazurkiewicz, Sur un ensemble ferm´e, punctiforme, qui rencontre toute droite passant par un certain domaine (Polish, French summary), Prace Mat.-Fiz. 27 (1916), 11–16.
- ↑ а б Dumitrescu, Adrian; Jiang, Minghui; Pach, János (2014), Opaque sets, Algorithmica, 69 (2): 315—334, doi:10.1007/s00453-012-9735-2, MR 3183418
- ↑ V. Akman, An algorithm for determining an opaque minimal forest of a convex polygon, Information Processing Letters, 24 (1987), 193—198.
- ↑ P. Dublish, An O(n3) algorithm for finding the minimal opaque forest of a convex polygon, Information Processing Letters, 29(5) (1988), 275—276.
- ↑ T. Shermer, A counterexample to the algorithms for determining opaque minimal forests, Information Processing Letters, 40 (1991), 41–42.
- ↑ J. S. Provan, M. Brazil, D. A. Thomas and J. F. Weng, Minimum opaque covers for polygonal regions, manuscript, October 2012, arXiv:1210.8139v1
- ↑ Dumitrescu, Adrian; Jiang, Minghui (2014), The opaque square, Proc. 30th Annual Symposium on Computational Geometry (SoCG'14), New York: Association for Computing Machinery, с. 529—538, arXiv:1311.3323, doi:10.1145/2582112.2582113, MR 3382335
- ↑ Beingessner, Alexis; Smid, Michiel (2012), Computing the coverage of an opaque forest (PDF), Proc. 24th Canadian Conference on Computational Geometry (CCCG'12), с. 95—100, архів оригіналу (PDF) за 21 вересня 2017, процитовано 2 вересня 2018
- ↑ Barba, Luis; Beingessner, Alexis; Bose, Prosenjit; Smid, Michiel (2013), Computing covers of plane forests (PDF), Proc. 25th Canadian Conference on Computational Geometry (CCCG'13), архів оригіналу (PDF) за 21 вересня 2017, процитовано 2 вересня 2018