Максимальное непересекающееся множество

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

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

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

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

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

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

При наличии набора C фигур приближение к MDS( C ) можно найти с помощью следующего жадного алгоритма :

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

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

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

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

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

Когда C — это набор интервалов на линии, M = 1, и, таким образом, жадный алгоритм находит точный MDS. Чтобы увидеть это, предположим wlog, что интервалы вертикальны, и пусть x — интервал с наивысшей нижней конечной точкой . Все остальные интервалы, пересекаемые x, должны пересекать его нижнюю конечную точку. Следовательно, все интервалы в N(x) пересекаются друг с другом, и MDS(N(x)) имеет размер не более 1 (см. рисунок).

Следовательно, в одномерном случае MDS можно найти точно за время O ( n  log  n ): ^[2]

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

Этот алгоритм аналогичен решению задачи интервального планирования с приоритетом самого раннего крайнего срока .

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

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

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

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

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

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

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

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

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

Пусть C — набор из n прямоугольников, параллельных осям, на плоскости, все с одинаковой высотой H , но с разной длиной. Следующий алгоритм находит непересекающийся набор с размером не менее |MDS( C )|/2 за время O ( n  log  n ): ^[2]

• Нарисуйте m горизонтальных линий так, чтобы:
  1. Расстояние между двумя линиями строго больше H.
  2. Каждая линия пересекает по крайней мере один прямоугольник (следовательно, m  ≤  n ).
  3. Каждый прямоугольник пересекается ровно одной линией.
• Поскольку высота всех прямоугольников равна H , невозможно, чтобы прямоугольник пересекался более чем одной линией. Поэтому линии разбивают множество прямоугольников на m подмножеств ( ) – каждое подмножество включает прямоугольники, пересекаемые одной линией.${\displaystyle R_{i},\ldots ,R_{m}}$
• Для каждого подмножества вычислите точный MDS, используя одномерный жадный алгоритм (см. выше).${\displaystyle R_{i}}$${\displaystyle М_{я}}$
• По построению прямоугольники в ( ) могут пересекать только прямоугольники в или в . Поэтому каждое из следующих двух объединений является непересекающимся множеством:${\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.

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

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

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

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

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

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

Чалермсук и Чузой ^[6] улучшили этот фактор до .${\displaystyle O(\log {\log {n}})}$

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

Долгое время не было известно, существует ли приближение с постоянным множителем для прямоугольников, параллельных осям, разной длины и высоты. Было высказано предположение, что такое приближение может быть найдено с помощью гильотинных разрезов . В частности, если существует гильотинное разделение прямоугольников, параллельных осям, в котором прямоугольники разделены, то его можно использовать в динамическом программном подходе для нахождения приближения с постоянным множителем для MDS. ^{[8] : sub.1.2}${\displaystyle \Омега (н)}$

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

• Джозеф С. Б. Митчелл представил 10-факторный алгоритм аппроксимации. Его алгоритм основан на разбиении плоскости на прямоугольники с отсеченными углами . ^[9]
• Гальвес, Хан, Мари, Мёмке, Питту и Визе представили алгоритм, разбивающий плоскость на более общий класс многоугольников. Это упрощает анализ и улучшает приближение к 6-фактору. Кроме того, они улучшили приближение к 3-фактору ^[10] , а затем к (2+ε)-фактору. ^[11]

Пусть C — набор из n квадратов или кругов одинакового размера. Хохбаум и Маасс ^[4] представили схему аппроксимации с полиномиальным временем для поиска MDS с использованием простой стратегии смещенной сетки. Она находит решение в пределах (1 − ε) от максимума за время n ^{O (1/ ε 2 )} и линейное пространство. Стратегия обобщается на любую коллекцию толстых объектов примерно одинакового размера (т. е. когда отношение максимального размера к минимальному ограничено константой).

Пусть C — набор из n толстых объектов , таких как квадраты или круги , произвольных размеров. Существует PTAS для поиска MDS на основе многоуровневого выравнивания сетки. Он был открыт двумя группами примерно в одно и то же время и описан двумя разными способами.

Алгоритм Эрлебаха, Янсена и Зайделя ^[12] находит непересекающееся множество размером не менее (1 − 1/ k ) ²  ⋅ |MDS( C )| за время n ^{O ( k 2 )} для каждой константы k  > 1. Он работает следующим образом.

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

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

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

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

Алгоритм Чана ^[5] находит непересекающееся множество размером не менее (1 − 2/ k )⋅|MDS( C )| за время n ^{O ( k )} для каждой константы k  > 1.

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

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

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

Если почти все объекты выровнены по k , мы можем просто отбросить объекты, которые не выровнены по k , и найти максимальное непересекающееся множество оставшихся объектов за время n ^{O ( k )} . Это приводит к приближению (1 −  e ), где 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). Можно доказать, что каждая метка будет выровнена по 2 k для как минимум k  − 2 значений  j . Теперь для каждого j отбросим объекты, которые не выровнены по k в сдвиге ( j / k , j / k ), и найдем максимальное непересекающееся множество оставшихся объектов. Назовем это множество A ( j ). Назовем реальное максимальное непересекающееся множество  A *. Тогда:

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

Следовательно, наибольшее A ( j ) имеет размер не менее: (1 − 2/ k )| A *|. Возвращаемое значение алгоритма — наибольшее A ( j ); коэффициент аппроксимации равен (1 − 2/ k ), а время выполнения равно n ^{O ( k )} . Мы можем сделать коэффициент аппроксимации настолько малым, насколько захотим, так что это PTAS .

Обе версии можно обобщить на d -измерения (с различными коэффициентами аппроксимации) и на весовой случай.

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

Пусть C — набор из n толстых объектов , таких как квадраты или круги, произвольных размеров. Чан ^[5] описал алгоритм, который находит непересекающийся набор размером не менее (1 −  O ( √ b ))⋅|MDS( C )| за время n ^{O ( b )} для каждой константы b  > 1.

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

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

• |MDS( C _внутри )| ≤ a |MDS( C )|
• |MDS( C _{снаружи} )| ≤ a|MDS( C )|
• |MDS( _{граница} C )| c √ | MDS( C ) |

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

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

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

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

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

${\displaystyle E(m)=0\ \ \ \ {\text{ если }}m\leq b}$

${\displaystyle E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{ если }}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}}.}$

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

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

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

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

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

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

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

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

Решение этой повторяющейся проблемы следующее:

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

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

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

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

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

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

См. также. ^[15]

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

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

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