Максимальный непересекающийся набор - Maximum disjoint set

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

Поиск MDS важен в таких приложениях, как автоматическое размещение меток, СБИС схемотехника и сотовая мультиплексирование с частотным разделением.

Каждый набор неперекрывающихся фигур представляет собой независимый набор в граф пересечений форм. Следовательно, проблема МДС - это частный случай максимальный независимый набор (MIS) проблема. Обе проблемы НП завершена, но найти MDS может быть проще, чем найти MIS в двух отношениях:

• Для общей проблемы MIS наиболее известные точные алгоритмы являются экспоненциальными. В некоторых геометрических графах пересечений есть субэкспоненциальные алгоритмы для поиска MDS.^[1]
• Общая проблема MIS трудна для аппроксимации и даже не имеет приближения постоянного множителя. В некоторых геометрических графах пересечений есть схемы полиномиальной аппроксимации (PTAS) для поиска MDS.

Задача MDS может быть обобщена путем присвоения разного веса каждой форме и поиска непересекающегося множества с максимальным общим весом.

В следующем тексте MDS (C) обозначает максимальное непересекающееся множество в множестве C.

Жадные алгоритмы

Учитывая набор C форм, приближение к МДС (C) можно найти по следующему жадный алгоритм:

• ИНИЦИАЛИЗАЦИЯ: Инициализировать пустой набор, S.
• ПОИСК: Для любой формы Икс в C:
  1. Рассчитать N (х) - подмножество всех фигур в C которые пересекаются Икс (включая Икс сам).
  2. Вычислите самый большой независимый набор в этом подмножестве: МДС (N (x)).
  3. Выберите Икс такой, что | MDS (N (x)) | сводится к минимуму.
• Добавлять Икс к S.
• Удалять Икс и N (х) из C.
• Если в C, вернитесь в поиск.
• КОНЕЦ: вернуть набор S.

Для любой формы Икс что мы добавляем к S, мы теряем формы в N (х), потому что они пересекаются Икс и поэтому не может быть добавлен к S позже. Однако некоторые из этих форм сами по себе пересекаются друг с другом, и поэтому в любом случае невозможно, чтобы все они находились в оптимальном решении. MDS (S). Наибольшее подмножество фигур, которые может все быть в оптимальном решении МДС (N (x)). Поэтому, выбирая Икс что сводит к минимуму | MDS (N (x)) | сводит к минимуму потери от добавления Икс к S.

В частности, если мы можем гарантировать, что есть Икс для которого | MDS (N (x)) | ограничено константой (скажем, M), то этот жадный алгоритм дает константу M-факторное приближение, так как мы можем гарантировать, что:

${\displaystyle |S|\geq {\frac {|MDS(C)|}{M}}}$

Такая верхняя граница M существует для нескольких интересных случаев:

1-мерные интервалы: точный полиномиальный алгоритм

Когда C это набор интервалов на линии, M= 1, и, таким образом, жадный алгоритм находит точную MDS. Чтобы увидеть это, предположим, что w.l.o.g. что интервалы вертикальны, и пусть Икс - интервал с самая высокая нижняя конечная точка. Все остальные интервалы пересекаются Икс должен пересечь нижнюю конечную точку. Следовательно, все интервалы в N (х) пересекаются друг с другом, и МДС (N (x)) имеет размер не более 1 (см. рисунок).

Следовательно, в одномерном случае МДС может быть найдена точно во времени О(п бревноп):^[2]

1. Отсортируйте интервалы в порядке возрастания их нижних конечных точек (это требует времени О(п бревноп)).
2. Добавьте интервал с самой высокой нижней конечной точкой и удалите все интервалы, пересекающие его.
3. Продолжайте, пока не перестанут быть интервалы.

Этот алгоритм аналогичен алгоритму самый ранний крайний срок первое планирование решение интервальное планирование проблема.

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

Толстые формы: приближения с постоянным коэффициентом

Когда C комплект единичных дисков, M=3,^[3] потому что крайний левый диск (диск, центр которого имеет наименьшее Икс координата) пересекает не более 3 других непересекающихся дисков (см. рисунок). Следовательно, жадный алгоритм дает 3-приближение, т.е. находит непересекающееся множество размером не менее МДС (С)/3.

Аналогично, когда C представляет собой набор параллельных осям единичных квадратов, M=2.

Когда C набор дисков произвольного размера, M= 5, поскольку диск наименьшего радиуса пересекает не более 5 других непересекающихся дисков (см. Рисунок).

Аналогично, когда C представляет собой набор параллельных осям квадратов произвольного размера, M=4.

Остальные константы можно рассчитать для других правильные многоугольники.^[3]

Алгоритмы разделяй и властвуй

Самый распространенный подход к поиску MDS - это разделять и властвовать. Типичный алгоритм этого подхода выглядит следующим образом:

1. Разделите данный набор фигур на два или более подмножества, чтобы фигуры в каждом подмножестве не могли перекрывать фигуры в других подмножествах по геометрическим соображениям.
2. Рекурсивно найдите MDS в каждом подмножестве отдельно.
3. Возвратите объединение MDS из всех подмножеств.

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

Прямоугольники, параллельные оси: приближение логарифмического коэффициента

Позволять C быть набором п параллельные оси прямоугольники на плоскости. Следующий алгоритм находит непересекающееся множество размером не менее ${\displaystyle {\frac {|MDS(C)|}{\log {n}}}}$ во время ${\displaystyle O(n\log {n})}$:^[2]

• ИНИЦИАЛИЗАЦИЯ: отсортируйте горизонтальные края заданных прямоугольников по их у-координата, а вертикальные ребра - их Икс-координат (этот шаг требует времени О(п бревноп)).
• СОСТОЯНИЕ ОСТАНОВА: Если есть не более п ≤ 2 фигур, вычислите MDS напрямую и вернитесь.
• РЕКУРСИВНАЯ ЧАСТЬ:
  1. Позволять ${\displaystyle x_{\mathrm {med} }}$ быть средним Икс-координат.
  2. Разделите прямоугольники ввода на три группы в соответствии с их отношением к строке. ${\displaystyle x=x_{\mathrm {med} }}$: те, которые находятся полностью слева от него (${\displaystyle R_{\mathrm {left} }}$), полностью справа (${\displaystyle R_{\mathrm {right} }}$), и пересекаемые им (${\displaystyle R_{\mathrm {int} }}$). По построению мощности ${\displaystyle R_{\mathrm {left} }}$ и ${\displaystyle R_{\mathrm {right} }}$ самое большее п/2.
  3. Рекурсивно вычислить приблизительный МДС в ${\displaystyle R_{\mathrm {left} }}$ (${\displaystyle M_{\mathrm {left} }}$) И в ${\displaystyle R_{\mathrm {right} }}$ (${\displaystyle M_{\mathrm {right} }}$), и вычислить их объединение. По построению прямоугольники в ${\displaystyle M_{\mathrm {left} }}$ и ${\displaystyle M_{\mathrm {right} }}$ все не пересекаются, поэтому ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$ - непересекающееся множество.
  4. Вычислить точный МДС в ${\displaystyle R_{\mathrm {int} }}$ (${\displaystyle M_{\mathrm {int} }}$). Поскольку все прямоугольники в ${\displaystyle R_{\mathrm {int} }}$ пересечь одну вертикальную линию ${\displaystyle x=x_{\mathrm {med} }}$, это вычисление эквивалентно нахождению MDS из набора интервалов и может быть решено точно за время O (п войти п) (см. выше).
• Вернуться либо ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$ или же ${\displaystyle M_{\mathrm {int} }}$ - какой из них больше.

По индукции доказывается, что на последнем шаге либо ${\displaystyle M_{\mathrm {left} }\cup M_{\mathrm {right} }}$ или же ${\displaystyle M_{\mathrm {int} }}$ иметь мощность не менее ${\displaystyle {\frac {|MDS(C)|}{\log {n}}}}$.

Фактор аппроксимации уменьшен до ${\displaystyle O(\log {\log {n}})}$^[4] и обобщен на случай, когда прямоугольники имеют разный вес.^[5]

Прямоугольники, параллельные осям, одинаковой высоты: 2-аппроксимация

Позволять C быть набором п параллельные оси прямоугольники в плоскости одинаковой высоты ЧАС но разной длины. Следующий алгоритм находит непересекающееся множество размером не менее | MDS (C) | / 2 по времени О(п бревноп):^[2]

• Рисовать м горизонтальные линии, такие, что:
  1. Расстояние между двумя линиями строго больше, чем ЧАС.
  2. Каждая линия пересекает хотя бы один прямоугольник (следовательно, м ≤ п).
  3. Каждый прямоугольник пересекает ровно одна линия.
• Поскольку высота всех прямоугольников равна ЧАС, прямоугольник не может быть пересечен более чем одной линией. Следовательно, прямые разбивают множество прямоугольников на м подмножества (${\displaystyle R_{i},\ldots ,R_{m}}$) - каждое подмножество включает прямоугольники, пересекаемые одной линией.
• Для каждого подмножества ${\displaystyle R_{i}}$, вычислить точную MDS ${\displaystyle M_{i}}$ с использованием одномерного жадного алгоритма (см. выше).
• По построению прямоугольники в (${\displaystyle R_{i}}$) может пересекать только прямоугольники в ${\displaystyle R_{i+1}}$ или в ${\displaystyle R_{i-1}}$. Следовательно, каждое из следующих двух объединений является непересекающимся множеством:
  • Союз нечетных МДС: ${\displaystyle M_{1}\cup M_{3}\cup \cdots }$
  • Союз четных МДС: ${\displaystyle M_{2}\cup M_{4}\cup \cdots }$
• Верните самый крупный из этих двух союзов. Его размер должен быть не менее | MDS | / 2.

Прямоугольники, параллельные осям, одинаковой высоты: PTAS

Позволять C быть набором п параллельные оси прямоугольники на плоскости, все одинаковой высоты, но разной длины. Существует алгоритм, который находит непересекающееся множество размером не менее | MDS (C)|/(1 + 1/k) во время О(п^2k−1), для каждой постоянной k > 1.^[2]

Алгоритм является усовершенствованием вышеупомянутого 2-приближения путем объединения динамическое программирование со сменной техникой.^[6]

Этот алгоритм можно обобщить на d размеры. Если метки имеют одинаковый размер во всех измерениях, кроме одного, можно найти похожее приближение, применив динамическое программирование по одному из измерений. Это также сокращает время до n ^ O (1 / e).^[7]

Толстые предметы одинакового размера: PTAS

Позволять C быть набором п квадраты или круги одинакового размера. Существует схема полиномиальной аппроксимации для поиска MDS с использованием простой стратегии со сдвигом сетки. Он находит решение в пределах (1 -е) максимума по времени п^О(1/е2) время и линейное пространство.^[6] Стратегия распространяется на любой набор толстые предметы примерно одинакового размера (т.е. когда отношение максимального размера к минимальному ограничено константой).

Жирные объекты произвольных размеров: PTAS

Позволять C быть набором п толстые предметы (например, квадраты или круги) произвольных размеров. Существует PTAS для поиска МДС на основе многоуровневого выравнивания сетки. Он был обнаружен двумя группами примерно в одно и то же время и описан двумя разными способами.

Версия 1 находит непересекающееся множество размером не менее (1 - 1 /k)² · | МДС (C) | во время п^О(k2), для каждой постоянной k > 1:^[8]

Масштабируйте диски так, чтобы наименьший из них имел диаметр 1. Разбейте диски по уровням на основе логарифма их размера. То есть, j-й уровень содержит все диски диаметром от (k + 1)^j и (k + 1)^j+1, за j ≤ 0 (самый маленький диск находится на уровне 0).

Для каждого уровня j, наложим на плоскость сетку, состоящую из линий (k + 1)^j+1 отдельно друг от друга. По своей конструкции каждый диск может пересекать не более одной горизонтальной линии и одной вертикальной линии от своего уровня.

Для каждого р, s от 0 до k, определять D(р,s) как подмножество дисков, которые не пересекаются ни одной горизонтальной линией, индекс которой по модулю k является р, ни вертикальной линией, индекс модуля которой k является s. Посредством принцип голубятни, есть хотя бы одна пара (г, с) такой, что ${\displaystyle |\mathrm {MDS} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {MDS} |}$, т.е. найти МДС можно только в D(р,s) и упустить лишь небольшую часть дисков в оптимальном решении:

• Для всех k² возможные значения р,s (0 ≤ р,s < k), вычислить D(р,s) с помощью динамическое программирование.
• Верните самый большой из них k² наборы.

Квадродерево региона с точечными данными

Версия 2 находит непересекающееся множество размером не менее (1 - 2 /k) · | МДС (C) | во время п^О(k), для каждой постоянной k > 1.^[7]

Алгоритм использует сдвинутый квадродеревья. Ключевое понятие алгоритма: выравнивание в сетку квадродерева. Объект размера р называется k-выровненный (куда k ≥ 1 - константа), если она находится внутри ячейки квадродерева размером не более кр (р ≤ кр).

По определению k-выровненный объект, который пересекает границу ячейки квадрата размером р должен иметь размер не менее р/k (р > р/k). Граница ячейки размера р можно покрыть 4k квадраты размера р/k; следовательно, количество непересекающихся жирных объектов, пересекающих границу этой ячейки, не превышает 4kc, куда c постоянное измерение жирности предметов.

Следовательно, если все предметы толстые и k-выровнен, можно найти точное максимальное непересекающееся множество во времени п^О(kc) используя алгоритм «разделяй и властвуй». Начните с ячейки квадродерева, содержащей все объекты. Затем рекурсивно разделите его на меньшие ячейки квадродерева, найдите максимум в каждой меньшей ячейке и объедините результаты, чтобы получить максимум в большей ячейке. Поскольку количество непересекающихся жирных объектов, пересекающих границу каждой ячейки квадродерева, ограничено 4kc, мы можем просто «угадать», какие объекты пересекают границу в оптимальном решении, а затем применить принцип «разделяй и властвуй» к объектам внутри.

Если почти все объекты k-aligned, мы можем просто отбросить объекты, которые не k-выровнен, и найти максимальный непересекающийся набор оставшихся объектов во времени п^О(k). Это приводит к (1 -е) приближения, где e - доля объектов, не являющихся k-выровнен.

Если большинство объектов не k-выровнены, можем попробовать сделать их k-выровнено смена сетка, кратная (1 /k,1/k). Во-первых, масштабируйте объекты так, чтобы все они находились в единичном квадрате. Затем рассмотрим k сдвиги сетки: (0,0), (1 /k,1/k), (2/k,2/k), ..., ((k − 1)/k,(k − 1)/k). Т.е. для каждого j в {0, ...,k - 1}, рассмотрим сдвиг сетки в (j / k, j / k). Можно доказать, что на каждой метке будет 2k-выровнен не менее k - 2 значенияj. Теперь для каждого j, выбросьте предметы, которые не k-выровнен в (j/k,j/k) сдвиг и найти максимальное непересекающееся множество остальных объектов. Назовите этот набор А(j). Реальное максимальное непересекающееся множество назовемА*. Потом:

${\displaystyle \sum _{j=0,\ldots ,k-1}{|A(j)|}\geq (k-2)|A*|}$

Поэтому самый крупный А(j) имеет размер не менее: (1-2 /k)|А* |. Возвращаемое значение алгоритма - наибольшее. А(j); коэффициент аппроксимации (1 - 2 /k), а время выполнения п^О(k). Мы можем сделать коэффициент приближения сколь угодно малым, так что это PTAS.

Обе версии можно обобщить на d размерности (с разными коэффициентами аппроксимации) и взвешенного корпуса.

Алгоритмы геометрического разделителя

Несколько алгоритмов «разделяй и властвуй» основаны на определенном геометрический разделитель теорема. Геометрический разделитель - это линия или фигура, которая разделяет данный набор фигур на два меньших подмножества, так что количество фигур, теряемых во время разделения, относительно невелико. Это позволяет как PTAS и субэкспоненциальные точные алгоритмы, как описано ниже.

Жирные объекты произвольных размеров: PTAS с использованием геометрических разделителей

Позволять C быть набором п толстые предметы произвольных размеров. Следующий алгоритм находит непересекающееся множество размером не менее (1 -О(√б)) · | МДС (C) | во время п^О(б), для каждой постоянной б > 1.^[7]

Алгоритм основан на следующей теореме о геометрическом разделителе, которая доказывается аналогично доказательство существования геометрического разделителя для непересекающихся квадратов:

Для каждого набора C толстых предметов есть прямоугольник, который разделяет C на три подмножества объектов - C_внутри, C_{за пределами} и C_{граница}, такое, что:

• | МДС (C_внутри)| ≤ а| МДС (C)|
• | МДС (C_{за пределами}) | ≤ a | MDS (C)|
• | МДС (C_{граница})| c√|МДС (C)|

куда а и c являются константами. Если бы мы могли вычислить MDS (C) точно, мы могли бы сделать постоянную а всего 2/3 за счет правильного выбора прямоугольника разделителя. Но поскольку мы можем только приблизить МДС (C) постоянным множителем постоянная а должен быть больше. К счастью, а остается постоянной, не зависящей от |C|.

Эта теорема о разделителе позволяет построить следующие PTAS:

Выберите константу б. Отметьте все возможные комбинации до б + 1 этикетка.

• Если | MDS (C) | имеет размер не более б (т.е. все наборы б + 1 метки не пересекаются), тогда просто верните этот MDS и выйдите. Этот шаг требует п^О(б) время.
• В противном случае используйте геометрический разделитель для разделения C к двум подмножествам. Найдите приблизительную MDS в C_внутри и C_{за пределами} отдельно и вернуть их комбинацию в качестве приблизительного MDS в C.

Позволять E(м) будет ошибкой вышеуказанного алгоритма, когда оптимальный размер MDS равен MDS (C) = м. Когда м ≤ б, ошибка равна 0, потому что максимальное непересекающееся множество вычисляется точно; когда м > б, ошибка увеличивается не более чем на c√м количество меток, пересекаемых разделителем. Худший случай для алгоритма - это когда разбиение на каждом шаге происходит в максимально возможном соотношении, которое а:(1 − а). Следовательно, функция ошибок удовлетворяет следующему рекуррентному соотношению:

${\displaystyle E(m)=0\ \ \ \ {\text{ if }}m\leq b}$

${\displaystyle E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ if }}m>b}$

Решение этого повторения:

${\displaystyle E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.}$

т.е. ${\displaystyle E(m)=O(m/{\sqrt {b}})}$. Мы можем сделать коэффициент приближения настолько малым, насколько захотим, путем правильного выбора б.

Этот PTAS более экономичен, чем PTAS на основе квадродеревьев, и может обрабатывать обобщение, когда объекты могут скользить, но не может обрабатывать взвешенный случай.

Диски с ограниченным соотношением размеров: точный субэкспоненциальный алгоритм

Позволять C быть набором п диски, такие, что отношение между наибольшим радиусом и наименьшим радиусом не более р. Следующий алгоритм находит MDS (C) точно в срок ${\displaystyle 2^{O(r\cdot {\sqrt {n}})}}$.^[9]

Алгоритм основан на геометрический разделитель с ограниченной шириной на съемочной площадке Q центров всех дисков в C. Эта теорема о разделителе позволяет построить следующий точный алгоритм:

• Найдите такую ​​разделительную линию, чтобы не более 2п/ 3 центра справа (C_верно), не более 2п/ 3 центра слева от него (C_{оставили}), и самое большее О(√п) центры находятся на расстоянии менее р/ 2 из строки (C_int).
• Рассмотрим все возможные неперекрывающиеся подмножества C_int. Есть не больше ${\displaystyle 2^{O(r\cdot {\sqrt {n}})}}$ такие подмножества. Для каждого такого подмножества рекурсивно вычислить MDS C_{оставили} и MDS C_верно, и вернуть наибольший комбинированный набор.

Время работы этого алгоритма удовлетворяет следующему рекуррентному соотношению:

${\displaystyle T(1)=1}$

${\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{ if }}n>1}$

Решение этого повторения:

${\displaystyle T(n)=2^{O(r\cdot {\sqrt {n}})}}$

Алгоритмы локального поиска

Псевдодиски: PTAS

А набор псевдодисков представляет собой набор объектов, в котором границы каждой пары объектов пересекаются не более двух раз. (Обратите внимание, что это определение относится ко всей коллекции и ничего не говорит о формах конкретных объектов в коллекции). Набор псевдодисков имеет ограниченную сложность союза, т.е. число точек пересечения на границе объединения всех объектов линейно от числа объектов.

Позволять C быть набором псевдодисков с п объекты. Следующее алгоритм локального поиска находит непересекающийся набор размером не менее ${\displaystyle (1-O({\frac {1}{\sqrt {b}}}))\cdot |MDS(C)|}$ во время ${\displaystyle O(n^{b+3})}$, для каждой целочисленной константы ${\displaystyle b\geq 0}$:^[10]

• ИНИЦИАЛИЗАЦИЯ: Инициализировать пустой набор, ${\displaystyle S}$.
• ПОИСК: перебрать все подмножества ${\displaystyle C-S}$ размер от 1 до ${\displaystyle b+1}$. Для каждого такого подмножества Икс:
  • Подтвердите это Икс сам по себе является независимым (иначе перейти к следующему подмножеству);
  • Рассчитать набор Y объектов в S которые пересекаются Икс.
  • Если ${\displaystyle |Y|<|X|}$, затем удалите Y из S и вставить Икс: ${\displaystyle S:=S-Y+X}$.
• КОНЕЦ: вернуть набор S.

Каждый обмен на этапе поиска увеличивает размер S не менее чем на 1, и, следовательно, может произойти не более п раз.

Алгоритм очень простой; трудная часть - доказать коэффициент приближения.^[10]

Смотрите также.^[11]

Алгоритмы релаксации линейного программирования

Псевдодиски: PTAS

Позволять C быть набором псевдодисков с п объекты и сложность объединения ты. С помощью релаксация линейного программирования, можно найти непересекающееся множество размером не менее ${\displaystyle {\frac {n}{u}}\cdot |MDS(C)|}$. Это возможно либо с помощью рандомизированного алгоритма, который имеет высокую вероятность успеха и время выполнения. ${\displaystyle O(n^{3})}$, или детерминированный алгоритм с более медленным временем выполнения (но все же полиномиальный). Этот алгоритм можно обобщить на взвешенный случай.^[10]

Другие классы форм, приближения которых известны

• Отрезки прямых в двумерной плоскости.^[11][12]
• Произвольный двумерный выпуклые объекты.^[11]
• Кривые с ограниченным количеством точек пересечения.^[12]

внешняя ссылка

• Аппроксимационные алгоритмы для максимально независимого набора псевдодисков - презентация Сариэль Хар-Пелед.
• Код Javascript для вычисления точного максимального непересекающегося набора прямоугольников.

Примечания

1. Ravi, S. S .; Хант, Х. Б. (1987). «Применение теоремы о плоском сепараторе к задачам счета». Письма об обработке информации. 25 (5): 317. Дои:10.1016/0020-0190(87)90206-7., Smith, W. D .; Вормальд, Н.С. (1998). «Теоремы о геометрическом разделителе и приложения». Материалы 39-го ежегодного симпозиума по основам компьютерных наук (каталожный номер 98CB36280). п. 232. Дои:10.1109 / sfcs.1998.743449. ISBN  978-0-8186-9172-0. S2CID  17962961.
2. Agarwal, P.K .; Ван Кревельд, М .; Сури, С. (1998). «Размещение метки максимально независимым набором в прямоугольниках». Вычислительная геометрия. 11 (3–4): 209. Дои:10.1016 / s0925-7721 (98) 00028-5. HDL:1874/18908.
3. Marathe, M. V .; Breu, H .; Хант, H. B .; Ravi, S. S .; Розенкранц, Д. Дж. (1995). «Простая эвристика для графов единичного диска». Сети. 25 (2): 59. arXiv:математика / 9409226. Дои:10.1002 / нетто.3230250205.
4. Chalermsook, P .; Чужой, Дж. (2009). «Максимально независимый набор прямоугольников». Материалы двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 892. Дои:10.1137/1.9781611973068.97. ISBN  978-0-89871-680-1.
5. Чалермсук, П. (2011). «Раскраска и максимально независимый набор прямоугольников». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Конспект лекций по информатике. 6845. С. 123–134. Дои:10.1007/978-3-642-22935-0_11. ISBN  978-3-642-22934-3.
6. Хохбаум, Д.С.; Маасс, В. (1985). «Аппроксимативные схемы для задач покрытия и упаковки в обработке изображений и СБИС». Журнал ACM. 32: 130–136. Дои:10.1145/2455.214106. S2CID  2383627.
7. Чан, Т. М. (2003). «Полиномиальные схемы аппроксимации для упаковки и прокалывания жировых предметов». Журнал алгоритмов. 46 (2): 178–189. CiteSeerX  10.1.1.21.5344. Дои:10.1016 / s0196-6774 (02) 00294-8.
8. Эрлебах, Т .; Jansen, K .; Зайдель, Э. (2005). "Схемы аппроксимации полиномиального времени для геометрических пересечений графов". SIAM Журнал по вычислениям. 34 (6): 1302. Дои:10.1137 / s0097539702402676.
9. Фу, Б. (2011). «Теория и применение геометрических разделителей с ограниченной шириной». Журнал компьютерных и системных наук. 77 (2): 379–392. Дои:10.1016 / j.jcss.2010.05.003.
10. Чан, Т.; Хар-Пелед, С. (2012). «Аппроксимационные алгоритмы для максимально независимого набора псевдодисков». Дискретная и вычислительная геометрия. 48 (2): 373. arXiv:1103.1431. Дои:10.1007 / s00454-012-9417-5. S2CID  38183751.
11. Agarwal, P.K .; Мустафа, Н. Х. (2006). «Независимый набор графов пересечений выпуклых объектов в 2D». Вычислительная геометрия. 34 (2): 83. Дои:10.1016 / j.comgeo.2005.12.001.
12. Fox, J .; Пач, Дж. Н. (2011). «Вычисление числа независимости графов пересечений». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 1161. CiteSeerX  10.1.1.700.4445. Дои:10.1137/1.9781611973082.87. ISBN  978-0-89871-993-2. S2CID  15850862.