Геометрическое несоответствие

Геометрическая теория несоответствия ^[1] является подразделом теории несоответствия , которая занимается балансировкой геометрических множеств, таких как интервалы или прямоугольники . Общий исследовательский вопрос в этой области: если задан набор точек в геометрическом пространстве и набор объектов в том же пространстве, можем ли мы раскрасить каждую точку в один из двух разных цветов (например, черный и белый) так, чтобы каждый объект содержал примерно одинаковое количество точек каждого цвета?

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

Интервалы

В простейшей геометрической настройке невязки множество объектов представляет собой множество всех подынтервалов действительного интервала [0,1]. В этой настройке можно достичь невязки 1: просто раскрасить точки попеременно черным - белым - черным - белым - и т. д. Тогда невязка каждого интервала будет равна 0 или 1.

Проблема становится более сложной, когда точки не доступны заранее, а поступают по одной, и каждая точка должна быть окрашена немедленно по прибытии. Такая настройка называется «Расхождение интервалов онлайн». Цзян, Кулкарни и Сингла доказывают, что: ^{[2] : Раздел 3.2}

• Ни один онлайн-алгоритм не может гарантировать постоянного расхождения.
• Случайное окрашивание каждой точки по мере ее поступления дает ожидаемое расхождение. ${\displaystyle {\tilde {O}}({\sqrt {n}})}$
• Если точка прибытия является состязательной, то расхождение любого онлайн-алгоритма составляет . ${\displaystyle \Omega ({\sqrt {n}})}$
• Если прибытие точки является стохастическим, то существует эффективный алгоритм, который гарантирует расхождение для некоторой универсальной константы c с высокой вероятностью (т.е. с вероятностью 1-1/poly( n ), где показатель степени полинома зависит от c ). ${\displaystyle O(n^{c/\log {\log {n}}})}$

Их доказательство использует сведение к проблеме балансировки онлайн-деревьев, которая является проблемой несоответствия, в которой набор объектов является набором поддеревьев полного m -арного дерева с высотой h . Для этой проблемы они доказывают, что если для достаточно большой константы C и m ≥ 100, то существует онлайн-алгоритм, который достигает несоответствия . ^{[2] : Раздел 2} ${\displaystyle h\leq {\log \log n}/C}$ ${\displaystyle O(\log ^{2}n)}$

Прямоугольники и коробки

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

• Бек ^[3] доказал, что расхождение составляет не менее Ω(log n ) и не более O(log ⁴ n ).
• Николов ^[4] доказал, что расхождение не превышает O(log ^1,5 n ).

Когда набор объектов представляет собой набор всех прямоугольников (возможно, повернутых), то:

• Бек ^[3] доказал, что расхождение составляет не менее Ω( n ^1/4-ε ) и не более O( n ^1/2+ε ) для любого ε >0.

Матоусек ^[5] изучал d -мерное расширение проблемы Туснади. Улучшая предыдущие результаты Рота, Шмидта, Бека, Богуса и Шринивасана, он доказал верхнюю границу простым доказательством. ${\displaystyle O_{d}((\log n)^{d+1/2}{\sqrt {\log \log n}})}$

Полоски

Когда набор объектов представляет собой набор полос — прямоугольников вида [a,b]x[0,1] и [0,1]x[a,b], то постановка задачи эквивалентна задаче «двух перестановок»: даны две перестановки на наборе из n элементов, и каждый элемент нужно раскрасить либо в черный, либо в белый цвет так, чтобы расхождение в каждом интервале каждой перестановки было минимальным (две перестановки — это порядок координат x и порядок координат y точек).

• Спенсер доказал, что можно достичь расхождения не более 2. ^[2]

Цзян, Кулкарни и Сингла ^[2] изучают онлайн-систему со стохастическим прибытием точки и доказывают, что:

• Случайная раскраска дает ожидаемое расхождение . ${\displaystyle {\tilde {O}}({\sqrt {n}})}$
• Существует эффективный алгоритм, который гарантирует расхождение для некоторой универсальной константы c с высокой вероятностью . Они показывают применение этого результата к онлайн-честному делению . ${\displaystyle O(n^{c/\log {\log {n}}})}$

Выпуклые многогранники

Матоусек ^[5] и Николов ^[4] изучали более общую ситуацию, где множество объектов индуцируется растяжениями и переносами фиксированного выпуклого многогранника . Он доказал верхние и нижние границы расхождения. Результаты аналогичны результатам для прямоугольников и коробок.

Полупространства

Когда множество объектов представляет собой множество полупространств в евклидовом d -мерном пространстве:

• Александер ^[5] доказал нижнюю границу для любого плотного множества точек, то есть отношение максимального и минимального внутренних расстояний составляет O( n ^{1/ d} ). ${\displaystyle \Omega (n^{1/2-d/2})}$
• Матоусек ^[6] доказал верхнюю границу . Фактически, эта верхняя граница справедлива не только для полупространств, но и для любой системы множеств, для которой первичная функция дробления находится в O( m ^d ). ${\displaystyle C_{d}n^{1/2-d/2}}$

Ссылки

1. Матушек, Иржи (1999). Геометрическое несоответствие: иллюстрированное руководство . Спрингер. ISBN 3-540-65528-X.
2. Цзян, Хаотянь; Кулкарни, Джанардхан; Сингла, Сахил (2019-10-02). «Онлайн-геометрическое расхождение для стохастических поступлений с применением к минимизации зависти». arXiv : 1910.01073 [cs.DS].
3. Beck, József (1981-12-01). "Сбалансированные двухцветные раскраски конечных множеств в квадрате I". Combinatorica . 1 (4): 327–335. doi :10.1007/BF02579453. ISSN  1439-6912.
4. Николов, Александр (январь 2017 г.). «Более точные оценки расхождения коробок и многогранников». Mathematika . 63 (3): 1091–1113. arXiv : 1701.05532 . doi :10.1112/S0025579317000250. ISSN  0025-5793.
5. Alexander, R. (1990-06-01). «Геометрические методы в изучении нерегулярностей распределения». Combinatorica . 10 (2): 115–136. doi :10.1007/BF02123006. ISSN  1439-6912.
6. Матоушек, Дж. (1995-06-01). «Жесткие верхние границы для расхождения полупространств». Дискретная и вычислительная геометрия . 13 (3): 593–601. doi :10.1007/BF02574066. ISSN  1432-0444.