Непрозрачный набор

Четыре непрозрачных набора на единицу площади . Вверху слева: его граница, длина 4. Вверху справа: Три стороны, длина 3. Внизу слева: дерево Штейнера вершин, длина $1+{\sqrt {3}}\approx 2.732$. Внизу справа: предполагаемое оптимальное решение, длина. ${\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639$.

В дискретной геометрии непрозрачный набор — это система кривых или другой набор на плоскости , который блокирует все линии обзора через многоугольник , круг или другую форму. Непрозрачные множества также называют барьерами , детекторами лучей , непрозрачными крышками или (в тех случаях, когда они имеют форму леса из отрезков линий или других кривых) непрозрачными лесами . Непрозрачные множества были представлены Стефаном Мазуркевичем в 1916 году. а проблема минимизации их общей длины была поставлена ​​Фредериком Багемилом в 1959 году.

Например, видимость через единичный квадрат может быть заблокирована четырьмя его граничными краями длиной 4, но более короткий непрозрачный лес блокирует видимость через квадрат длиной ${\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639$. Не доказано, является ли это кратчайшим возможным непрозрачным набором для квадрата, и для большинства других фигур эта проблема также остается нерешенной. Кратчайшее непрозрачное множество для любого ограниченного выпуклого множества на плоскости имеет длину не более периметра множества и не менее половины периметра. Для квадрата известна чуть более сильная нижняя граница, чем половина периметра. Другое выпуклое множество, непрозрачные множества которого обычно изучаются, — это единичный круг , для которого кратчайшее связное непрозрачное множество имеет длину $2+\pi$. Без предположения связности кратчайшее непрозрачное множество для круга имеет длину не менее $\pi$ и самое большее $4.7998$.

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

Определения

Каждый набор $S$ в плоскости блокирует видимость через надмножество $S$, его охват $C$. $C$ состоит из точек, для которых все прямые, проходящие через точку, пересекаются $S$. Если заданный набор $K$ образует подмножество охвата $S$, затем $S$ Говорят, что это непрозрачный набор , барьер , детектор луча или непрозрачная крышка для $K$. Если, кроме того, $S$ имеет особый вид, состоящий из конечного числа отрезков , объединение которых образует лес , он называется непрозрачным лесом . Для любого заданного множества существует множество возможных непрозрачных множеств. $K$, включая $K$ сам по себе и множество возможных непрозрачных лесов. Для непрозрачных лесов или, шире, для систем спрямляемых кривых , их длину можно измерить стандартным способом. Для более общих наборов точек можно использовать одномерную меру Хаусдорфа , которая согласуется со стандартной длиной в случаях отрезков линий и спрямляемых кривых.

Большинство исследований по этой проблеме предполагают, что данный набор $K$ представляет собой выпуклое множество . Когда оно не выпуклое, а просто связное множество , его можно заменить выпуклой оболочкой, не меняя непрозрачных множеств. Некоторые варианты проблемы ограничивают непрозрачное множество тем, что оно полностью лежит внутри или полностью снаружи. $K$. В этом случае его называют внутренним барьером или внешним барьером соответственно. Если это не указано, предполагается, что барьер не имеет ограничений на свое местоположение. Рассмотрены также варианты задачи, в которых непрозрачное множество должно быть связным или образовывать единую кривую. Неизвестно, каждое ли выпуклое множество $P$ имеет кратчайшее непрозрачное множество, или вместо этого длины его непрозрачных множеств могут приближаться к нижней грани, даже не достигая ее. Каждый непрозрачный набор для $P$ по длине может быть сколь угодно близко аппроксимирован непрозрачным лесом, высказывалась гипотеза, что кратчайшим непрозрачным множеством каждого выпуклого многоугольника является непрозрачный лес, но это не было доказано.

Границы

Когда покрываемая область представляет собой выпуклое множество , длина его кратчайшего непрозрачного множества должна составлять не менее половины его периметра и не более его периметра. Для некоторых регионов могут быть сделаны дополнительные улучшения этих границ.

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

Если $K$ — ограниченное выпуклое множество, которое необходимо покрыть, то его граница $\partial K$ образует непрозрачное множество, длина которого равна периметру $|\partial K|$. Следовательно, минимально возможная длина непрозрачного набора не превышает периметра. Для наборов $K$ которые строго выпуклы, что означает, что на границе нет отрезков прямых, а для внутренних барьеров эта граница точная. Каждая точка на границе должна содержаться в непрозрачном множестве, поскольку через каждую точку границы проходит касательная линия , которая не может быть заблокирована никакими другими точками. Те же рассуждения показывают, что для внутренних барьеров выпуклых многоугольников все вершины должны быть включены. Следовательно, минимальное дерево Штейнера вершин представляет собой кратчайшее связное непрозрачное множество, а путь коммивояжера вершин представляет собой кратчайшее непрозрачное множество с одной кривой . Однако для внутренних барьеров неполигональных выпуклых множеств, которые не являются строго выпуклыми, или для барьеров, соединение которых не требуется, другие непрозрачные множества могут быть короче; например, всегда можно опустить самый длинный сегмент линии границы. В этих случаях периметр или длина дерева Штейнера обеспечивают верхнюю границу длины непрозрачного множества.

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

Существует несколько доказательств того, что непрозрачное множество для любого выпуклого множества $K$ должна иметь общую длину не менее $|\partial K|/2$, половина периметра. Одна из самых простых предполагает формулу Крофтона , согласно которой длина любой кривой пропорциональна ожидаемому количеству ее точек пересечения со случайной линией из соответствующего распределения вероятностей на линиях. Удобно упростить задачу, аппроксимируя $K$ строго выпуклым надмножеством, периметр которого можно выбрать сколь угодно близким к исходному множеству. Тогда, кроме касательных к $K$ (которые составляют исчезающую часть всех линий), линию, пересекающую $K$ дважды пересекает его границу. Следовательно, если случайная прямая пересекает $K$ с вероятностью $p$, ожидаемое количество пересечений границы равно $2p$. Но каждая линия, которая пересекается $K$ пересекает свое непрозрачное множество, поэтому ожидаемое количество пересечений с непрозрачным множеством не менее $p$, что как минимум вдвое меньше, чем для $K$. По формуле Крофтона длины границы и барьера имеют ту же пропорцию, что и эти ожидаемые числа.

Эта нижняя граница $|\partial K|/2$ О длине непрозрачного множества нельзя улучшить, чтобы он имел постоянный коэффициент больше, чем 1/2, поскольку существуют примеры выпуклых множеств, у которых есть непрозрачные множества, длина которых близка к этой нижней границе. В частности, для очень длинных тонких прямоугольников одна длинная сторона и две короткие стороны образуют барьер, общую длину которого можно сделать сколь угодно близкой к половине периметра. Поэтому среди нижних границ, учитывающих только периметр области покрытия, граница $|\partial K|/2$ лучше всего. Однако, приближаясь к $|\partial K|/2$ Таким образом, необходимо рассматривать последовательность фигур, а не просто одну фигуру, поскольку для любого выпуклого множества $K$ это не треугольник, существует $\delta$ такие, что все непрозрачные множества имеют длину не менее $|\partial K|/2+\delta$.

Конкретные формы

Для треугольника , как и для любого выпуклого многоугольника, кратчайшим связным непрозрачным множеством является его минимальное дерево Штейнера. В случае треугольника это дерево можно описать явно: если самый широкий угол треугольника равен $2\pi /3$ (120°) или более, он использует две кратчайшие ребра треугольника, а в противном случае он состоит из трех отрезков линий, идущих от вершин до точки Ферма треугольника. Однако без предположения связности оптимальность дерева Штейнера не была продемонстрирована. Изуми доказал небольшое улучшение нижней границы деления периметра пополам для равностороннего треугольника .

Нерешенная задача по математике :

Каковы кратчайшие непрозрачные множества для единичного квадрата и единичного круга?

(еще нерешенные задачи по математике)

Для единичного квадрата периметр равен 4, периметр минус самое длинное ребро равен 3, а длина минимального дерева Штейнера равна $1+{\sqrt {3}}\approx 2.732$. Однако известен более короткий несвязный непрозрачный лес длиной ${\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639$. Он состоит из минимального дерева Штейнера, состоящего из трех вершин квадрата, а также отрезка, соединяющего четвертую вершину с центром. Росс Хонсбергер приписывает свое открытие Морису Пуарье, канадскому школьному учителю. но он уже был описан Джонсом в 1962 и 1964 годах. Известно, что он оптимален среди лесов, содержащих всего две компоненты: и предполагалось, что это наилучший вариант в целом, но это остается недоказанным. Нижняя граница деления периметра пополам для квадрата, равная 2, уже доказанная Джонсом: можно немного улучшить, чтобы $2.00002$, для любого барьера, состоящего из не более чем счетного числа спрямляемых кривых , улучшение аналогичных предыдущих границ, которые ограничивали размещение барьера только рядом с заданным квадратом.

Непрозрачные леса для единичного круга. Слева: U-образный оптимальный связанный барьер длиной $2+\pi$. Справа: лучший из известных барьеров, состоящий из трех компонентов и длины. $\approx 4.7998$.

Случай единичного круга был описан в Scientific American колонке 1995 года Яном Стюартом с решением длины $2+\pi$, оптимально для одной кривой или связанного барьера но не для непрозрачного леса с множеством кривых. Вэнс Фабер и Ян Мисельски приписывают это решение с одной кривой Менахему Магидору в 1974 году. К 1980 году Э. Макай уже предложил лучшее трехкомпонентное решение длиной примерно $4.7998$, вновь открыт Джоном Дэем в продолжение колонки Стюарта. Неизвестная длина оптимального решения была названа константой обнаружения луча .

Алгоритмы

Два опубликованных алгоритма утверждают, что генерируют оптимальный непрозрачный лес для произвольных многоугольников, основанные на идее, что оптимальное решение имеет особую структуру: дерево Штейнера для одного треугольника в триангуляции многоугольника и сегмент в каждом оставшемся треугольнике из одной вершины. к противоположной стороне длиной, равной высоте треугольника. Эта структура соответствует предполагаемой структуре оптимального решения для квадрата. Хотя оптимальная триангуляция для решения этой формы не является частью входных данных этих алгоритмов, ее можно найти с помощью алгоритмов за полиномиальное время с использованием динамического программирования . Однако эти алгоритмы не решают задачу правильно для всех полигонов, поскольку некоторые полигоны имеют более короткие решения с иной структурой, чем те, которые они находят. В частности, для длинного тонкого прямоугольника минимальное дерево Штейнера со всеми четырьмя вершинами короче, чем решение на основе триангуляции, которое находят эти алгоритмы. Ни один известный алгоритм не может гарантированно найти правильное решение проблемы, независимо от времени его работы.

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

Приближение

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

• Для общих непрозрачных множеств они предоставляют алгоритм, коэффициент аппроксимации которого не превышает $${\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1.5868.$$ Общая идея алгоритма состоит в том, чтобы построить барьер, подобный «луку и стрелам», из ограничивающей рамки с минимальным периметром входных данных, состоящий из многоугольной цепи, натянутой вокруг многоугольника от одного угла ограничивающей рамки до противоположного угла, вместе с отрезком, соединяющим третий угол ограничивающей рамки с диагональю рамки.
• Для непрозрачных множеств, состоящих из одной дуги, они предлагают алгоритм, степень аппроксимации которого не превышает $${\frac {\pi +5}{\pi +2}}\approx 1.5835.$$ Результирующий барьер определяется опорной линией входной фигуры. Входной сигнал проецируется перпендикулярно на интервал этой линии, а барьер соединяет две конечные точки этого интервала U-образной кривой, натянутой вокруг входного сигнала, как оптимальный связанный барьер для круга. Алгоритм использует вращающиеся штангенциркули для поиска опорной линии, для которой длина результирующего барьера минимальна.
• Для связных непрозрачных множеств они предоставляют алгоритм, коэффициент аппроксимации которого не превышает $1.5716$. Этот метод сочетает в себе однодуговой барьер со специальной обработкой фигур, близких к равностороннему треугольнику , для которого дерево Штейнера треугольника представляет собой более короткий связный барьер.
• Для внутренних барьеров они предоставляют алгоритм, коэффициент аппроксимации которого не превышает $1.7168$. Идея состоит в том, чтобы использовать предложенное Шермером обобщение структуры неверных ранее алгоритмов (дерево Штейнера на подмножестве точек вместе с сегментами высоты для триангуляции оставшихся входных данных). с быстрой аппроксимацией для части аппроксимации, связанной с деревом Штейнера.

Кроме того, поскольку кратчайший связный внутренний барьер выпуклого многоугольника задается минимальным деревом Штейнера, он имеет схему аппроксимации с полиномиальным временем .

Покрытие

Район, покрытый данным лесом, можно определить следующим образом:

• Найдите выпуклую оболочку каждой связной компоненты леса.
• Для каждой вершины $p$ корпуса, проведите линию по кругу вокруг $p$, подразделяющий плоскость на клинья, в которых линия стреловидности пересекает один из корпусов, и клинья, в которых линия стреловидности пересекает плоскость без препятствий. Объединение покрытых клиньев образует множество $C_{p}$.
• Найдите пересечение всех множеств $C_{p}$. Это пересечение является покрытием леса.

Если вход состоит из $n$ формирование сегментов линий $m$ связные компоненты, то каждый из $n$ наборы $C_{p}$ состоит максимум из $2m$ клинья. Отсюда следует, что комбинаторная сложность области покрытия и время ее построения равны $O(m^{2}n^{2})$ как выражено в большой записи О.

Хотя этот алгоритм является оптимальным в худшем случае для входных данных, область покрытия которых имеет комбинаторную сложность, соответствующую этой границе, на практике этот алгоритм может быть эвристически улучшен с помощью этапа предварительной обработки, который объединяет перекрывающиеся пары оболочек до тех пор, пока все оставшиеся оболочки не станут непересекающимися во времени. $O(n\log ^{2}n)$. Если это сводит входные данные к одному корпусу, нет необходимости запускать более дорогостоящий алгоритм развертки и пересечения: в этом случае корпусом является область покрытия.

Наборы опаков без кривизны

Первые четыре этапа конструкции Багемила фрактальных непрозрачных множеств для единичного квадрата.

Мазуркевич (1916) показал, что непрозрачное множество может не содержать каких-либо нетривиальных кривых и при этом иметь конечную общую длину. Упрощенная конструкция Багемила (1959) , показанная на рисунке, дает пример единичного квадрата. Построение начинается с отрезков линий, образующих непрозрачное множество с дополнительным свойством: отрезки отрицательного наклона блокируют все линии неотрицательного наклона, а отрезки положительного наклона блокируют все линии неположительного наклона. На рисунке исходными отрезками с этим свойством являются четыре непересекающихся отрезка по диагоналям квадрата. Затем он неоднократно подразделяет эти сегменты, сохраняя при этом это свойство. На каждом уровне построения каждый отрезок разбивается небольшим разрывом вблизи своей середины на два отрезка с наклоном одного знака, которые вместе перекрывают все линии противоположного знака, заблокированные исходным отрезком. Предельное множество этой конструкции представляет собой канторово пространство , которое, как и все промежуточные этапы конструкции, является непрозрачным множеством для квадрата. При быстро уменьшающихся размерах зазоров конструкция образует набор, Размерность Хаусдорфа равна единице, и одномерная мера Хаусдорфа (понятие длины, подходящее для таких множеств) конечна.

Наборы расстояний границы квадрата или четырехсегментного кратчайшего известного непрозрачного множества для квадрата содержат все расстояния в интервале от 0 до ${\sqrt {2}}$. Однако, используя подобные фрактальные конструкции, также можно найти фрактальные непрозрачные множества, наборы расстояний которых исключают бесконечное количество расстояний в этом интервале или которые (в предположении гипотезы континуума ) образуют набор нулевой меры .

История

Непрозрачные множества первоначально изучал Стефан Мазуркевич в 1916 году. Другие ранние работы по непрозрачным множествам включают статьи Его Величества Сена Гупты и Н.К. Басу Мазумдара в 1955 году: и Фредериком Багемилом в 1959 году, но речь идет в первую очередь о наборах расстояний и топологических свойствах барьеров, а не о минимизации их длины. В постскриптуме к своей статье Багемил запросил минимальную длину внутреннего барьера площади: и последующая работа в основном была сосредоточена на вариантах проблемы, связанных с минимизацией длины. Их неоднократно формулировали с множеством красочных формулировок: рыть траншею как можно меньшей длины, чтобы найти прямой закопанный телефонный кабель, пытаясь найти ближайшую прямую дорогу, заблудившись в лесу, доплыть до прямой береговой линии, потерявшись в море, эффективная покраска стен, чтобы сделать стеклянный дом непрозрачным, и т. д.

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

См. также

• Беллман заблудился в лесу
• сад Евклида