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

Форма, которая блокирует все линии обзора

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

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

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

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

Определения

Каждое множество в плоскости блокирует видимость через надмножество , его покрытие . состоит из точек, для которых все линии, проходящие через точку, пересекаются . Если данное множество образует подмножество покрытия , то оно называется непрозрачным множеством , барьером , детектором луча или непрозрачным покрытием для . Если, кроме того, имеет специальную форму, состоящую из конечного числа отрезков прямых , объединение которых образует лес , оно называется непрозрачным лесом . Существует множество возможных непрозрачных множеств для любого данного множества , включая его самого, и множество возможных непрозрачных лесов. Для непрозрачных лесов или, в более общем смысле, для систем спрямляемых кривых их длина может быть измерена стандартным способом. Для более общих множеств точек может быть использована одномерная мера Хаусдорфа , которая согласуется со стандартной длиной в случаях отрезков прямых и спрямляемых кривых. ^[3] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle K}$

Большинство исследований этой проблемы предполагает, что заданное множество является выпуклым множеством . Когда оно не выпуклое, а просто связное множество , его можно заменить его выпуклой оболочкой, не меняя его непрозрачных множеств. Некоторые варианты проблемы ограничивают непрозрачное множество тем, что оно лежит полностью внутри или полностью снаружи . В этом случае оно называется внутренним барьером или внешним барьером соответственно. Когда это не указано, предполагается, что барьер не имеет ограничений на свое местоположение. Также рассматривались версии проблемы, в которых непрозрачное множество должно быть связным или образовывать одну кривую. Неизвестно, имеет ли каждое выпуклое множество кратчайшее непрозрачное множество, или же вместо этого длины его непрозрачных множеств могут приближаться к инфимуму, никогда не достигая его. ^[3] Каждое непрозрачное множество для может быть сколь угодно близко аппроксимировано по длине непрозрачным лесом, ^[4] и было высказано предположение, что каждый выпуклый многоугольник имеет непрозрачный лес в качестве своего кратчайшего непрозрачного множества, но это не было доказано. ^[3] ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle P}$

Границы

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

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

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

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

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

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

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

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

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

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

(еще нерешенные проблемы по математике)

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

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

Случай единичной окружности был описан в колонке Scientific American 1995 года Яном Стюартом с решением длиной , ^[15] оптимальным для одной кривой или связанного барьера ^{[8] [16] [17]} но не для непрозрачного леса с несколькими кривыми. Вэнс Фабер и Ян Мычельски приписывают это решение с одной кривой Менахему Магидору в 1974 году. ^[8] К 1980 году Э. Макай уже предоставил лучшее трехкомпонентное решение с длиной приблизительно , ^​​[18] переоткрытое Джоном Дэем в продолжении колонки Стюарта. ^[19] Неизвестная длина оптимального решения была названа константой обнаружения луча . ^[20] ${\displaystyle 2+\pi }$ ${\displaystyle 4.7998}$

Алгоритмы

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

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

Приближение

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

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

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

Покрытие

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

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

Если вход состоит из отрезков линий, образующих связные компоненты, то каждый из наборов состоит не более чем из клиньев. Из этого следует, что комбинаторная сложность области покрытия и время ее построения выражаются в нотации O big . ^[25] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle C_{p}}$ ${\displaystyle 2m}$ ${\displaystyle O(m^{2}n^{2})}$

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

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

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

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

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

История

Непрозрачные множества были первоначально изучены Стефаном Мазуркевичем в 1916 году. ^[1] Другие ранние работы по непрозрачным множествам включают статьи HM Sen Gupta и NC Basu Mazumdar в 1955 году, ^[27] и Фредерика Багемила в 1959 году, ^[2] но они в основном о расстояниях множеств и топологических свойствах барьеров, а не о минимизации их длины. В постскриптуме к своей статье Багемил спросил о минимальной длине внутреннего барьера для квадрата, ^[2] и последующая работа в основном была сосредоточена на версиях задачи, включающих минимизацию длины. Они неоднократно ставились с несколькими красочными формулировками: рытье траншеи как можно меньшей длины, чтобы найти прямой зарытый телефонный кабель, ^[8] попытка найти близлежащую прямую дорогу, заблудившись в лесу, ^[17] плавание к прямой береговой линии, заблудившись в море, ^[4] эффективная покраска стен, чтобы сделать стеклянный дом непрозрачным, ^[28] и т. д.

Проблема также была обобщена на множества, которые блокируют все геодезические на римановом многообразии , ^{[29] [30]} или которые блокируют линии через множества в более высоких размерностях. В трех измерениях соответствующий вопрос требует набора поверхностей минимальной общей площади, который блокирует всю видимость через твердое тело. Однако для некоторых твердых тел, таких как шар, неясно, существует ли такой набор, или вместо этого площадь имеет инфимум , который не может быть достигнут. ^{[8] [31]}

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

• Проблема Беллмана о заблудившемся в лесу
• Фруктовый сад Эвклида

Ссылки

1. Мазуркевич, Стефан (1916), «Sur ООН ансамбль ферме, пунктиформе, qui rencontre toute droite passant par un определенный домен», Prace Mat.-Fiz. (на польском и французском языках), 27 : 11–16.
2. Bagemihl, F. (1959), «Некоторые непрозрачные подмножества квадрата», Michigan Mathematical Journal , 6 (2): 99–103, doi :10.1307/mmj/1028998183, MR  0105657
3. Прован, Дж. Скотт; Бразилия, Маркус; Томас, Дорин ; Вэн, Цзя Ф. (2012), Минимальные непрозрачные покрытия для полигональных областей , arXiv : 1210.8139 , Bibcode : 2012arXiv1210.8139P
4. Думитреску, Адриан; Цзян, Минхуэй; Пах, Янош (2014), «Непрозрачные множества», Algorithmica , 69 (2): 315–334, arXiv : 1005.2218 , doi : 10.1007/s00453-012-9735-2, MR  3183418, S2CID  13884553
5. Kawohl, Bernd (1997), "Непрозрачный квадрат и непрозрачный круг", в Bandle, Catherine ; Everitt, William N.; Losonczi, Laszlo; Walter, Wolfgang (ред.), Общие неравенства, 7 (Oberwolfach, 1995) , Международная серия численной математики, т. 123, Базель: Birkhäuser , стр. 339–346, doi :10.1007/978-3-0348-8942-1_27, ISBN 978-3-0348-9837-9, МР  1457290
6. Думитреску, Адриан; Цзян, Минхуэй (2014), «Непрозрачный квадрат», Труды 30-го ежегодного симпозиума по вычислительной геометрии (SoCG'14) , Нью-Йорк: Ассоциация вычислительной техники, стр. 529–538, arXiv : 1311.3323 , doi : 10.1145/2582112.2582113, ISBN 978-1-4503-2594-3, MR  3382335, S2CID  207211457
7. Кавамура, Акитоши; Морияма, Соноко; Отачи, Йота; Пах, Янош (2019), «Нижняя граница непрозрачных множеств» (PDF) , Computational Geometry , 80 : 13–22, doi : 10.1016/j.comgeo.2019.01.002, MR  3945133
8. Faber, V. ; Mycielski, J. (1986), «Кратчайшая кривая, которая пересекает все линии, пересекающие выпуклое тело», The American Mathematical Monthly , 93 (10): 796–801, doi :10.2307/2322935, JSTOR  2322935, MR  0867106
9. Нахин, Пол Дж. (2021), «Глава 7: Начало современной эпохи», Когда меньше — лучше: как математики открыли множество умных способов сделать вещи настолько маленькими (или настолько большими), насколько это возможно , Princeton University Press , стр. 279–330, doi : 10.2307/j.ctv19qmf43.12, JSTOR  j.ctv19qmf43.12
10. Идзуми, Тайсуке (2016), «Улучшение нижней границы непрозрачных множеств для равностороннего треугольника», Дискретная прикладная математика , 213 : 130–138, doi : 10.1016/j.dam.2016.05.006 , MR  3544574
11. Хонсбергер, Росс (1978), «Задача 12: Непрозрачный квадрат», Mathematical Morsels , The Dolciani Mathematical Expositions, т. 3, Нью-Йорк: Математическая ассоциация Америки , стр. 22–25, ISBN 978-0-88385-303-0, МР  0490615
12. Jones, Robert Edward Douglas (1962), "Глава 4: Непрозрачные подмножества квадрата", Линейная мера и непрозрачные множества, Ретроспективные диссертации и тезисы, т. 2058, Университет штата Айова , стр. 36–45, doi :10.31274/rtd-180813-2223
13. Jones, RED (1964), «Непрозрачные множества степени », The American Mathematical Monthly , 71 : 535–537, doi : 10.2307/2312596, JSTOR  2312596, MR  0164898 ${\displaystyle \alpha }$
14. Каволь, Бернд (2000), «Некоторые проблемы оптимизации невыпуклой формы», Оптимальное проектирование формы (Tróia, 1998) , Lecture Notes in Mathematics, т. 1740, Берлин: Springer , стр. 7–46, doi :10.1007/BFb0106741, ISBN 978-3-540-67971-4, г-н  1804684
15. Стюарт, Ян (сентябрь 1995 г.), «Великое ограбление дренажной системы», Scientific American , 273 (3): 206–207, Bibcode : 1995SciAm.273c.206S, doi : 10.1038/scientificamerican0995-206, JSTOR  24981805
16. Эгглстон, Х. Г. (1982), «Максимальный радиус вписанной окружности выпуклого покрытия плоского связного множества заданной длины», Труды Лондонского математического общества , Третья серия, 45 (3): 456–478, doi :10.1112/plms/s3-45.3.456, MR  0675417
17. Joris, H. (1980), «Le chasseur perdu dans la forêt», Elemente der Mathematik (на французском языке), 35 (1): 1–14, MR  0559167; переведено на английский язык Стивеном Финчем, arXiv :1910.00615
18. Макай, Э. младший (1980), «О двойственной задаче Тарского о доске», 2-й коллоквиум по дискретной геометрии , Институт математики Зальцбургского университета, стр. 127–132, Zbl  459.52005
19. Стюарт, Ян (февраль 1996 г.), «Обратная связь», Scientific American , 274 (2): 125, JSTOR  24989406
20. Финч, Стивен Р. (2003), «8.11 Константа обнаружения луча», Математические константы , Энциклопедия математики и ее приложений, Cambridge University Press , стр. 515–519, ISBN 978-0-521-81805-6
21. Акман, Варол (1987), «Алгоритм определения непрозрачного минимального леса выпуклого многоугольника», Information Processing Letters , 24 (3): 193–198, doi :10.1016/0020-0190(87)90185-2, MR  0882227, S2CID  37582183
22. Дублиш, Пратул (1988), « Алгоритм нахождения минимального непрозрачного леса выпуклого многоугольника», Information Processing Letters , 29 (5): 275–276, doi :10.1016/0020-0190(88)90122-6, MR  0981078 ${\displaystyle O(n^{3})}$
23. Shermer, Thomas (1991), «Контрпример к алгоритмам определения непрозрачных минимальных лесов», Information Processing Letters , 40 (1): 41–42, doi :10.1016/S0020-0190(05)80008-0, MR  1134007
24. Думитреску, Адриан; Цзян, Минхуэй; Тот, Чаба Д. (2015), «Вычисление непрозрачных внутренних барьеров в стиле Шермера», SIAM Journal on Discrete Mathematics , 29 (3): 1372–1386, doi : 10.1137/14098805X, hdl : 10211.3/198469 , MR  3376125
25. Beingessner, Alexis; Smid, Michiel (2012), «Вычисление покрытия непрозрачного леса» (PDF) , Труды 24-й Канадской конференции по вычислительной геометрии (CCCG'12) , стр. 95–100
26. Барба, Луис; Бинеджеснер, Алексис; Бозе, Просенжит ; Смид, Михиль (2013), «Вычисление покрытий планарных лесов» (PDF) , Труды 25-й Канадской конференции по вычислительной геометрии (CCCG'13)
27. Сен Гупта, HM ; Басу Мазумдар, NC (1955), «Заметка о некоторых плоских множествах точек», Бюллетень Калькуттского математического общества , 47 : 199–201, MR  0080287
28. Смарт, Дж. Р. (апрель 1966 г.), «Поиск математических талантов в Висконсине, II», The American Mathematical Monthly , 73 (4): 401–409, doi : 10.2307/2315418, JSTOR  2315418; см. Задачи 4, задача 5, стр. 405
29. Крофт, Х.Т. (1969), «Кривые, пересекающие некоторые множества больших окружностей на сфере», Журнал Лондонского математического общества , Вторая серия, 1 : 461–469, doi :10.1112/jlms/s2-1.1.461, MR  0247601
30. Азимов, Дэниел; Гервер, Джозеф Л. (2008), «Минимальные непрозрачные многообразия», Geometriae Dedicata , 133 : 67–82, doi : 10.1007/s10711-008-9234-4, MR  2390069, S2CID  122556952
31. Бракке, Кеннет А. (1992), «Проблема непрозрачного куба», The American Mathematical Monthly , 99 (9): 866–871, doi :10.2307/2324127, JSTOR  2324127, MR  1191707