Проблема непрозрачного леса - Opaque forest problem

В вычислительная геометрия, то проблема непрозрачного леса можно сформулировать следующим образом: "Учитывая выпуклый многоугольник C на плоскости определить минимальный лес Т замкнутых, ограниченных отрезков, таких, что каждая прямая C также пересекает Т ". Т считается непрозрачный лес, или же барьер из C. C считается покрытие из Т. В то время как любой лес, который покрывает C это барьер C, мы хотим найти ту, которая имеет наименьшую длину.

Может случиться так, что Т ограничен быть строго внутренним или внешним по отношению к C. В этом случае мы специально называем барьер как интерьер или же внешний вид. В противном случае предполагается, что у барьера нет ограничений на его расположение.

Несколько непрозрачных лесов на единицу площади. Слева вверху: периметр квадрата, длина 4. Справа вверху: периметр квадрата без одного края, длина 3. Слева внизу: Дерево Штейнера вершин, длина 1 +√3. Внизу справа: предполагаемое оптимальное решение, длина √2 + √6/2.

История и сложность

Проблема непрозрачного леса была первоначально введена Мазуркевич в 1916 г.^[1] С тех пор не было достигнуто большого прогресса в отношении исходной проблемы. Не существует любой Выверено общее решение проблемы. Фактически, оптимальное решение даже для простых фиксированных входов, таких как единичный квадрат или равносторонний треугольник, неизвестно. Существуют предполагаемые оптимальные решения для обоих этих случаев, но в настоящее время нам не хватает инструментов, чтобы доказать, что они оптимальны.^[2]Хотя общие решения проблемы были заявлены несколькими людьми,^[3]^[4]они либо не прошли экспертную оценку, либо оказались неверными.^[5]^[6]

Границы оптимального решения

Учитывая выпуклый многоугольник C с периметром п можно ограничить значение оптимального решения с точки зрения п. Эти границы, как правило, жесткие по отдельности, но из-за различных форм, которые могут быть предоставлены, они довольно слабы по отношению друг к другу.

В общем, можно доказать, что п/ 2 ≤ | OPT | ≤п.

Верхняя граница

Отслеживание периметра C всегда достаточно, чтобы покрыть это. Следовательно, п является верхней границей для любого C. Для внутренних барьеров эта граница жесткая в предельном случае, когда C это круг; каждая точка q по периметру круга должны находиться в Тили касательная C можно провести через q без пересечения Т. Однако для любого другого выпуклого многоугольника это неоптимально, а это означает, что это не особенно хорошая верхняя граница для большинства входных данных.

Для большинства входных данных несколько лучшую верхнюю границу выпуклых многоугольников можно найти по длине периметра, за вычетом самого длинного края (который является минимальное остовное дерево ). Еще лучше, можно взять минимальное дерево Штейнера вершин многоугольника. Для внутренних барьеров единственный способ улучшить эту границу - создать отключенный барьер.

Нижняя граница

Различные доказательства нижней оценки можно найти в Думитреску и Цзян (2014). Чтобы увидеть, что это в целом туго, можно рассмотреть случай растягивания очень длинного и тонкого прямоугольника. Любой непрозрачный лес для этой формы должен быть по крайней мере такой же длины, как прямоугольник, в противном случае есть отверстие, через которое могут проходить вертикальные линии. По мере того как прямоугольник становится длиннее и тоньше, это значение приближается к п/ 2. Следовательно, эта оценка, вообще говоря, жесткая. Однако для любой формы, которая на самом деле имеет положительную площадь, необходимо выделить некоторую дополнительную длину, чтобы охватить форму в других направлениях. Следовательно, это не очень хорошая нижняя граница для большинства входных данных.

Особые случаи

Для единичного квадрата эти границы равны 2 и 4 соответственно. Однако немного улучшены нижние оценки 2 + 10⁻¹² для барьеров, удовлетворяющих ограничению местности, и 2 + 10⁻⁵ для внутренних барьеров.^[7]

Приближения

Из-за трудностей, возникающих при нахождении оптимального барьера даже для простых примеров, стало очень желательно найти барьер, который приближается к оптимальному в пределах некоторого постоянного множителя.

Думитреску, Цзян и Пач (2014) предоставить несколько линейных приближений для оптимального решения. Для общих барьеров они обеспечивают 1/2 + (2 +√2)/ $π$ = 1,5867 ... коэффициент аппроксимации. Для подключенных барьеров это соотношение улучшено до 1,5716. Если барьер ограничен одной дугой, они достигают ( $π$ + 5)/( $π$ + 2) = коэффициент аппроксимации 1,5834.

Проверка барьеров и расчет покрытия лесов

Большинство барьерных конструкций таковы, что гарантировано покрытие желаемой области. Однако при произвольном барьере Т, хотелось бы подтвердить, что он покрывает желаемую площадьC.

В качестве простого первого прохода можно сравнить выпуклые оболочки из C и Т. Т покрывает не более чем его выпуклую оболочку, так что если выпуклая оболочка Т не содержит строго C, то он не может покрыть Т. Это дает простой O (п бревноп) алгоритм первого прохода для проверки барьера. Если Т состоит из одной компоненты связности, то она покрывает в точности ее выпуклую оболочку, и этого алгоритма достаточно. Однако если Т содержит более одного подключенного компонента, он может покрывать меньше. Так что этого теста в целом недостаточно.

Проблема определения, в каких именно регионах тот или иной лес Т состоящий из м подключенные компоненты и п отрезки фактически покрывают, можно решить в Θ (м²п²) время.^[8]Основная процедура для этого проста: сначала упростите каждый компонент связности, заменив его собственной выпуклой оболочкой. Тогда для вершины п каждой выпуклой оболочки проведите круговую развертку плоскости с линией с центром в п, отслеживание того, проходит ли линия через выпуклую оболочку или нет (не включая точку п сам). Ориентация линии развертки, во время которой произошло пересечение, дает набор точек в форме "солнца" (набор двойных клиньев с центром в п). Охват Т является точным пересечением всех этих "солнц" для всех вариантов выборап.

Хотя этот алгоритм является оптимальным в худшем случае, он часто делает много бесполезной работы, когда в этом нет необходимости. В частности, когда сначала вычисляются выпуклые оболочки, многие из них могут перекрываться. Если это так, их можно заменить их комбинированным выпуклым корпусом без потери общности. Если после слияния всех перекрывающихся корпусов образовался единственный барьер, то более общий алгоритм запускать не нужно; покрытие барьера - это самое большее его выпуклая оболочка, и мы только что определили, что его покрытие является его выпуклая оболочка. Объединенные оболочки могут быть вычислены за O (пбревно²п) время. Если осталось более одного корпуса, исходный алгоритм можно запустить на новом упрощенном наборе корпусов, чтобы сократить время работы.^[9]

Смотрите также

Фруктовый сад евклида