Геометрический разделитель

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

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

Разделители, представляющие собой линии

Общий вопрос

В 1979 году Хельге Тверберг поднял следующий вопрос. ) для двух целых положительных чисел k , l Каково наименьшее число n ( k , l , такое что для любого семейства попарно непересекающихся выпуклых объектов на плоскости существует прямая линия, которой находится не менее k на одной стороне объектов и по крайней мере я на другой стороне?

Известны следующие результаты.

• Очевидно, n (1,1)=1.
• Надежда и Качальский доказал, что n ( k ,1) ⩽ 12( k -1) для всех k ≥ 2.
• Жители деревни доказал, что n(2,2) = ∞: он показал бесконечное семейство попарно непересекающихся отрезков такое, что ни одна прямая не имеет по два отрезка на каждой стороне. Пах и Тардос продемонстрировал более простую конструкцию с использованием только единичных сегментов и другую конструкцию с использованием только дисков (или квадратов).

Разделители для осе-параллельных прямоугольников

Учитывая набор из N = 4 k непересекающихся прямоугольников, параллельных осям, на плоскости, существует линия, горизонтальная или вертикальная, такая, что по крайней мере N /4 прямоугольников полностью лежат с каждой стороны от нее (таким образом, не более N /2 прямоугольников пересекаются разделительной линией).

Доказательство

Определите W как самую западную вертикальную линию, по крайней мере, с N /4 прямоугольниками, полностью расположенными к западу от нее. Есть два случая:

• имеется не менее N Если к востоку от W /4 прямоугольников , то W — вертикальный разделитель.
• В противном случае, переместив W немного на запад, мы получим вертикальную линию, пересекающую более чем N /2 прямоугольников. Найдите точку на этой линии, у которой есть не менее N /4 прямоугольников вверху и N /4 прямоугольников под ней, и проведите через нее горизонтальный разделитель.

Оптимальность

Количество пересекающихся фигур, гарантированное приведенной выше теоремой, равно O( N ). Эта верхняя граница асимптотически точна, даже если фигуры представляют собой квадраты, как показано на рисунке справа. Это резко контрастирует с верхней границей O( √ N ) пересекающихся фигур, которая гарантируется, когда сепаратор представляет собой замкнутую форму (см. предыдущий раздел ).

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

Обобщения

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

Для данных N , параллельных осям, d -блоков внутренняя часть которых имеет толщину k , существует гиперплоскость, параллельная осям, такая, что по крайней мере:

$\lfloor (N+1-k)/(2d)\rfloor$

внутренностей d -box лежат по обе стороны от гиперплоскости.

В частном случае, когда k = N − 1 (т. е. каждая точка содержится не более чем в N − 1 ящики), имеет место следующая теорема:

Для данных N , параллельных осям, d -блоков внутренняя часть которых имеет толщину ( N - 1), существует гиперплоскость, параллельная осям, которая разделяет два из них.

Объекты не обязательно должны быть прямоугольниками, а разделители не обязательно должны быть параллельны оси:

Пусть C — набор возможных ориентаций гиперплоскостей (т. е. C = {горизонтальный, вертикальный}). Для заданных N d -объектов, таких, что каждые два непересекающихся объекта разделены гиперплоскостью с ориентацией из C , внутренняя часть которой имеет k -толщину, существует гиперплоскость с ориентацией из C такая, что по крайней мере: ( N + 1 − k )/O( C ) внутренностей d -объектов целиком лежат по обе стороны от гиперплоскости.

Алгоритмические версии

Найти гиперплоскости, гарантированные приведенными выше теоремами, можно за O( Nd ) шагов. Кроме того, если 2d списки нижних и верхних конечных точек интервалов, определяющих i- е координаты ящиков, предварительно отсортированы, то лучшая такая гиперплоскость (согласно широкому спектру мер оптимальности) может быть найдена в O( Nd ) шаги.

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

Простой случай, в котором гарантировано существование разделителя, следующий:

Учитывая набор из n непересекающихся осе-параллельных квадратов на плоскости, существует прямоугольник R такой, что не более 2 n /3 квадратов находятся внутри R , не более 2 n /3 квадратов находятся вне R , и при большинство O(sqrt( n )) квадратов не находятся внутри и не снаружи R (т.е. пересекают границу R ).

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

Доказательство

Определите прямоугольник толщиной 2 дюйма как прямоугольник, параллельный осям, с соотношением сторон не более 2.

Пусть R ₀ — прямоугольник минимальной площади с толщиной 2 дюйма, содержащий центры не менее n /3 квадратов. Таким образом, каждый 2-жирный прямоугольник размером меньше R ₀ содержит менее n /3 квадратов.

Для каждого t в [0,1) пусть R _t будет 2-жирным прямоугольником с тем же центром, что и R ₀ , увеличенным на 1 + t .

• R _t содержит R ₀ , поэтому он содержит центры как минимум n /3 квадратов.
• R _t менее чем в два раза больше, чем R ₀ , поэтому его можно покрыть двумя прямоугольниками толщиной 2, меньшими, чем R ₀ . Каждый из этих 2-жирных прямоугольников содержит в центрах менее n /3 квадратов. Следовательно, R _t содержит центры размером менее 2 n /3 квадратов.

Теперь осталось показать, что существует t , для которого R _t пересекает не более O(sqrt( n )) квадратов.

Сначала рассмотрим все «большие квадраты» – квадраты, длина стороны которых не менее $\operatorname {width} (R_{0})/2{\sqrt {n}}$. Для каждого t периметр R _t не превышает 2 · периметра ( R ₀ ), что составляет не более 6 · ширины ( R ₀ ), поэтому он может пересекаться не более $12{\sqrt {n}}$ большие квадраты.

Далее рассмотрим все «маленькие квадраты» – квадраты, длина стороны которых меньше $\operatorname {width} (R_{0})/2{\sqrt {n}}$.

Для каждого t определите: intersect( t маленьких квадратов, пересекаемых границей Rt _{) как набор} . Для каждого t ₁ и t ₂ , если $|t_{1}-t_{2}|\geq 1/{\sqrt {n}}$, затем $|\operatorname {width} (R_{t_{1}})-\operatorname {width} (R_{t_{2}})|\geq \operatorname {width} (R_{0})/{\sqrt {n}}$. Таким образом, существует разрыв как минимум $\operatorname {width} (R_{0})/2{\sqrt {n}}$ границей Rt _{1 и} границей Rt _{2 между} . Следовательно, intersect( t ₁ ) и intersect( t ₂ ) не пересекаются. Поэтому:

$\sum _{j=0}^{{\sqrt {n}}-1}{|\operatorname {intersect} (j/{\sqrt {n}})|}\leq n$

Следовательно, по принципу «ячейки» существует некоторый j ₀ , для которого:

$|\operatorname {intersect} (j_{0}/{\sqrt {n}})|\leq {\sqrt {n}}$

Разделитель, который мы ищем, — это прямоугольник R _t , где $t=j_{0}/{\sqrt {n}}$.

Пример приложения

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

• Разделите входной набор квадратов на два непересекающихся подмножества;
• Решите задачу по каждому подмножеству отдельно;
• Объедините решения двух подзадач и получите приближенное решение исходной задачи.

Обобщения

Приведенную выше теорему можно обобщить разными способами, возможно, с разными константами. Например:

• Вместо квадратов входная коллекция может содержать произвольные толстые объекты , такие как: круги, прямоугольники с ограниченным соотношением сторон и т.п.
• Вместо двумерных фигур на плоскости входная коллекция может содержать объекты любого измерения, и они могут располагаться в d -мерном торе .
• Вместо требования, чтобы фигуры во входной коллекции были непересекающимися, мы можем поставить более слабое требование, чтобы коллекция была:
  • k-thick , т. е. каждая точка покрыта не более чем k различными фигурами.
  • lk-thick , т. е. каждая точка покрыта не более k различными фигурами с соотношением размеров (размер наибольшей фигуры, разделенный на размер наименьшей формы) не более l .
  • k-перегружены , т. е. для любого поднабора фигур сумма их отдельных мер не более чем в k раз превышает меру их объединения.
• Вместо прямоугольного разделителя разделитель может иметь любую форму, которую можно покрыть меньшими копиями самого себя.
• Вместо ограничения количества фигур на каждой стороне разделителя можно ограничить любую меру, удовлетворяющую определенным аксиомам.

Оптимальность

Соотношение 1:2 в приведенной выше теореме о квадратном разделителе является лучшим, что можно гарантировать: существуют коллекции фигур, которые невозможно разделить в лучшем соотношении с помощью разделителя, который пересекает только фигуры O(sqrt( n )). Вот один из таких наборов (из теоремы 34 ):

Рассмотрим равносторонний треугольник . В каждую из трех его вершин поместите N /3 фигур, расположенных по экспоненциальной спирали так, чтобы диаметр увеличивался в постоянный коэффициент при каждом витке спирали, и каждая фигура касалась своих соседей по спирали. Например, начните с прямоугольника размером 1 на Φ, где Φ — золотое сечение . Добавьте соседний квадрат размером Φ на Φ и получите еще один золотой прямоугольник. Добавьте соседний квадрат размером (1+Φ) на (1+Φ) и получите золотой прямоугольник большего размера, и так далее.

Теперь, чтобы разделить более 1/3 фигур, разделитель должен отделить O( N ) фигур от двух разных вершин. Но для этого разделитель должен пересекать фигуры O( N ).

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

Пусть Q — набор из n точек на плоскости такой, что минимальное расстояние между точками равно d . Пусть a >0 — константа.

Существует пара параллельных прямых на расстоянии a не более 2 n /3 точек и не более такая, что с каждой стороны полосы лежит $1.3{a \over d}{\sqrt {n}}$ точки лежат внутри полосы.

Эквивалентно: существует прямая, по обе стороны от которой лежит не более 2n / 3 точек и не более $1.3{a \over d}{\sqrt {n}}$ точки лежат на расстоянии менее а /2 от него.

Эскиз доказательства

Определим центральную точку Q как точку o такую, что каждая прямая, проходящая через нее, имеет не более 2n / 3 точек Q на каждой стороне. Существование центральной точки можно доказать с помощью теоремы Хелли .

Для данной точки p и константы a > 0 определите Pr(a,p,o) как вероятность того, что случайная линия, проходящая через o, находится на расстоянии меньшем, чем a от p . Идея состоит в том, чтобы ограничить эту вероятность и, таким образом, ограничить ожидаемое количество точек на расстоянии меньше a от случайной линии до o . Тогда по принципу «ячейки» хотя бы одна строка через o является искомым разделителем.

Приложения

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

Геометрические сепараторы и сепараторы плоских графов

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

См. также

• Теорема о сэндвиче Хэма : учитывая n измеримых объектов в n -мерном пространстве, можно разделить их все пополам (относительно их меры, то есть объема) с помощью одной ( n - 1)-мерной гиперплоскости.
• Гильотинное разделение : задача разделения выпуклых объектов на плоскости с помощью гильотинных разрезов.
• Другие теоремы разделения .
• Одновременный разделитель: разделитель, который одновременно разделяет фигуры в нескольких коллекциях и одновременно пересекает небольшое количество фигур в каждой коллекции, может не всегда существовать.