K-набор (геометрия)

Точки, отделенные от других линией

Множество из шести точек (красные), его шесть 2-множеств (множества точек, содержащиеся в синих овалах) и линии, отделяющие каждое 2-множество от остальных точек (пунктирные черные). ${\displaystyle k}$

В дискретной геометрии -множество конечного множества точек в евклидовой плоскости представляет собой подмножество элементов , которое может быть строго отделено от остальных точек линией . В более общем смысле, в евклидовом пространстве более высоких размерностей -множество конечного множества точек представляет собой подмножество элементов , которое может быть отделено от остальных точек гиперплоскостью . В частности, когда (где - размер ), линия или гиперплоскость, отделяющая -множество от остальной части , является линией деления пополам или плоскостью деления пополам . ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle S}$

-множества множества точек на плоскости связаны проективной двойственностью с -уровнями в расположении прямых . -уровень в расположении прямых на плоскости — это кривая, состоящая из точек, которые лежат на одной из прямых и имеют ровно прямые под собой. Дискретные и вычислительные геометры также изучали уровни в расположениях более общих видов кривых и поверхностей. ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Комбинаторные границы

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

Каково наибольшее возможное число линий деления пополам для набора точек на плоскости? ${\displaystyle n}$

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

При анализе геометрических алгоритмов важно ограничить число -множеств плоского множества точек ^[2] или, что эквивалентно, число -уровней плоской конфигурации линий, проблема, впервые изученная Ловасом ^[3] и Эрдёшем и др. ^[4] Лучшая известная верхняя граница для этой проблемы равна , как показал Тамал Дей ^[5] с использованием неравенства числа пересечений Айтая, Хватала , Ньюборна и Семереди . Однако лучшая известная нижняя граница далека от верхней границы Дея: она равна для некоторой константы , как показал Тот. ^[6] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$ ${\textstyle \Omega (nc^{\sqrt {\log k}})}$ ${\displaystyle c}$

В трех измерениях наилучшая известная верхняя граница равна , а наилучшая известная нижняя граница равна . ^[7] Для точек в трех измерениях, которые находятся в выпуклом положении , то есть являются вершинами некоторого выпуклого многогранника, число -множеств равно , что следует из аргументов, используемых для ограничения сложности диаграмм Вороного th-го порядка. ^[8] ${\displaystyle O(nk^{3/2})}$ ${\textstyle \Omega (nkc^{\sqrt {\log k}})}$ ${\displaystyle k}$ ${\displaystyle \Theta {\bigl (}(n-k)k{\bigr )}}$ ${\displaystyle k}$

Для случая, когда (деление пополам прямых), максимальное число комбинаторно различных прямых, проходящих через две точки, которые делят пополам оставшиеся точки, равно ${\displaystyle k=n/2}$ ${\displaystyle S}$ ${\displaystyle k=1,2,\dots }$

1,3,6,9,13,18,22... (последовательность A076523 в OEIS ).

Также были доказаны границы для числа -множеств, где -множество является -множеством для некоторого . В двух измерениях максимальное число -множеств равно ровно , ^[9] тогда как в измерениях граница равна . ^[10] ${\displaystyle \leq k}$ ${\displaystyle \leq k}$ ${\displaystyle j}$ ${\displaystyle j\leq k}$ ${\displaystyle \leq k}$ ${\displaystyle nk}$ ${\displaystyle d}$ ${\displaystyle O(n^{\lfloor d/2\rfloor }k^{\lceil d/2\rceil })}$

Алгоритмы построения

Эдельсбруннер и Вельцль ^[11] впервые изучили проблему построения всех -множеств входного набора точек или, двойственно, построения -уровня расположения. -уровневую версию их алгоритма можно рассматривать как алгоритм плоской развертки , который строит уровень слева направо. Рассматриваемый в терминах -множеств наборов точек, их алгоритм поддерживает динамическую выпуклую оболочку для точек по обе стороны разделительной линии, многократно находит касательную к двум этим оболочкам и перемещает каждую из двух точек касания в противоположную оболочку. Чан ^[12] рассматривает последующие результаты по этой проблеме и показывает, что ее можно решить за время, пропорциональное границе Дея для сложности -уровня . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$ ${\displaystyle k}$

Агарвал и Матушек описывают алгоритмы для эффективного построения приближенного уровня; то есть кривой, которая проходит между -уровнем и -уровнем для некоторого малого параметра аппроксимации . Они показывают, что такое приближение может быть найдено, состоящим из ряда отрезков прямой, которые зависят только от и не зависят от или . ^[13] ${\displaystyle (k-\delta )}$ ${\displaystyle (k+\delta )}$ ${\displaystyle \delta }$ ${\displaystyle n/\delta }$ ${\displaystyle n}$ ${\displaystyle k}$

Матроидные обобщения

Проблему планарного -уровня можно обобщить до задачи параметрической оптимизации в матроиде : дан матроид, в котором каждый элемент взвешен линейной функцией параметра , и необходимо найти минимальный весовой базис матроида для каждого возможного значения . Если изобразить весовые функции в виде линий на плоскости, -уровень расположения этих линий будет отображаться как функция веса наибольшего элемента в оптимальном базисе в однородном матроиде , и Дей показал, что его оценка сложности -уровня может быть обобщена для подсчета количества различных оптимальных баз любого матроида с элементами и рангом . ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle O(nk^{1/3})}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Например, та же верхняя граница справедлива для подсчета числа различных минимальных остовных деревьев, сформированных в графе с ребрами и вершинами, когда ребра имеют веса, которые линейно изменяются с параметром . Эта параметрическая задача минимального остовного дерева изучалась различными авторами и может использоваться для решения других задач оптимизации бикритериальных остовных деревьев. ^[14] ${\displaystyle O(nk^{1/3})}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \lambda }$

Однако наиболее известная нижняя граница для параметрической задачи минимального остовного дерева — это , более слабая граница, чем для задачи -множества. ^[15] Для более общих матроидов верхняя граница Дея имеет соответствующую нижнюю границу. ^[16] ${\displaystyle \Omega (n\log k)}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$

Примечания

1. Агарвал, Аронов и Шарир (1997); Чан (2003); Чан (2005а); Чан (2005б).
2. Шазелл и Препарата (1986); Коул, Шарир и Яп (1987); Эдельсбруннер и Вельцль (1986).
3. Ловас 1971.
4. Эрдёш и др. 1973.
5. Дей 1998.
6. Тот 2001.
7. Шарир, Смородинский и Тардос 2001.
8. Ли (1982); Кларксон и Шор (1989).
9. Алон и Дьёри 1986.
10. Кларксон и Шор 1989.
11. Эдельсбруннер и Вельцль 1986.
12. Чан 1999.
13. Агарвал (1990); Матушек (1990); Матушек (1991).
14. Гасфилд (1980); Исии, Сиоде и Нисида (1981); Като и Ибараки (1983); Хасин и Тамир (1989); Фернандес-Бака, Слуцки и Эппштейн (1996); Чан (2005c).
15. Эппштейн 2022.
16. Эппштейн 1998.

Ссылки

• Агарвал, П. К. (1990). «Разбиение схем линий I: Эффективный детерминированный алгоритм». Дискретная и вычислительная геометрия . 5 (1): 449–483. doi : 10.1007/BF02187805 .
• Агарвал, П. К.; Аронов , Б .; Шарир, М. (1997). «Об уровнях в расположениях прямых, отрезков, плоскостей и треугольников». Труды 13-го ежегодного симпозиума по вычислительной геометрии . С. 30–38.
• Алон, Н.; Дьёри, Э. (1986). «Число малых полупространств конечного множества точек на плоскости». Журнал комбинаторной теории . Серия A. 41 : 154–157. doi : 10.1016/0097-3165(86)90122-6 .
• Чан, ТМ (1999). "Замечания об алгоритмах k-уровня на плоскости". Архивировано из оригинала 2010-11-04.
• Чан, ТМ (2003). «Об уровнях в расположениях кривых». Дискретная и вычислительная геометрия . 29 (3): 375–393. doi : 10.1007/s00454-002-2840-2 .
• Чан, ТМ (2005а). «Об уровнях в расположениях кривых, II: простое неравенство и его следствие». Дискретная и вычислительная геометрия . 34 : 11–24. doi : 10.1007/s00454-005-1165-3 .
• Чан, ТМ (2005b). «Об уровнях в расположениях поверхностей в трех измерениях». Труды 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 232–240.
• Чан, ТМ (2005c). «Поиск кратчайшего ребра узкого места в параметрическом минимальном остовном дереве». Труды 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 232–240.
• Шазелл, Б.; Препарата , Ф.П. (1986). «Поиск в диапазоне полупространства: алгоритмическое применение k-множеств». Дискретная и вычислительная геометрия . 1 (1): 83–93. doi : 10.1007/BF02187685 . MR  0824110.
• Кларксон, К. Л.; Шор , П. (1989). «Применение случайной выборки, II». Дискретная и вычислительная геометрия . 4 : 387–421. doi : 10.1007/BF02187740 .
• Коул, Р.; Шарир, М .; Яп, К.К. (1987). «О k -оболочках и связанных с ними проблемах». Журнал SIAM по вычислениям . 16 (1): 61–77. doi :10.1137/0216005. MR  0873250.
• Дей, ТК (1998). «Улучшенные оценки для плоских k-множеств и связанных с ними проблем». Дискретная и вычислительная геометрия . 19 (3): 373–382. doi : 10.1007/PL00009354 . MR  1608878.
• Эдельсбруннер, Х.; Вельцль , Э. (1986). «Построение поясов в двумерных конфигурациях с приложениями». Журнал SIAM по вычислениям . 15 (1): 271–284. doi :10.1137/0215019.
• Эппштейн, Д. (1998). "Геометрические нижние границы для параметрической оптимизации матроида" (PDF) . Дискретная и вычислительная геометрия . 20 (4): 463–476. doi : 10.1007/PL00009396 .
• Эппштейн, Дэвид (август 2022 г.). «Сильная нижняя граница параметрических минимальных остовных деревьев». Algorithmica . 85 (6): 1738–1753. arXiv : 2105.05371 . doi : 10.1007/s00453-022-01024-9 .
• Erdős, P. ; Lovász, L. ; Simmons, A.; Straus, EG (1973). "Графы диссекции плоских точечных множеств". Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) . Амстердам: North-Holland. стр. 139–149. MR  0363986.
• Фернандес-Бака, Д.; Слуцки, Г.; Эппштейн, Д. (1996). «Использование разрежения для параметрических задач минимального остовного дерева». Nordic Journal of Computing . 3 (4): 352–366.
• Гасфилд, Д. (1980). Анализ чувствительности для комбинаторной оптимизации . Технический представитель UCB/ERL M80/22. Калифорнийский университет в Беркли.
• Хассин, Р.; Тамир, А. (1989). «Максимизация классов двухпараметрических целей по матроидам». Математика исследования операций . 14 (2): 362–375. doi :10.1287/moor.14.2.362.
• Ишии, Х.; Сиоде, С.; Нисида, Т. (1981). «Стохастическая задача остовного дерева». Дискретная прикладная математика . 3 (4): 263–273. doi : 10.1016/0166-218X(81)90004-4 .
• Като, Н.; Ибараки, Т. (1983). Об общем числе опорных точек, необходимых для некоторых параметрических комбинаторных задач оптимизации . Рабочий документ 71. Ин-т экономических исследований, Кобеский университет коммерции.
• Ли, Дер-Цай (1982). «О диаграммах Вороного с k -ближайшими соседями на плоскости». IEEE Transactions on Computers . 31 (6): 478–487. doi :10.1109/TC.1982.1676031.
• Ловас, Л. (1971). «О количестве половинных линий». Annales Universitatis Scientiarum Buddhainensis de Rolando Eőtvős Nominatae Sectio Mathematica . 14 : 107–108.
• Матоушек, Й. (1990). «Построение ε-сетей». Дискретная и вычислительная геометрия . 5 (5): 427–448. doi : 10.1007/BF02187804 . MR  1064574.
• Матоушек, Дж. (1991). «Приблизительные уровни в линейных расположениях». Журнал SIAM по вычислениям . 20 (2): 222–227. doi :10.1137/0220013.
• Шарир, М.; Смородинский, С.; Тардос, Г. (2001). «Улучшенная граница для k-множеств в трех измерениях». Дискретная и вычислительная геометрия . 26 (2): 195–204. doi : 10.1007/s00454-001-0005-3 .
• Tóth, G. (2001). «Точечные множества с множеством k-множеств». Дискретная и вычислительная геометрия . 26 (2): 187–194. doi : 10.1007/s004540010022 .

Внешние ссылки

• Разделение пополам линий и k-множеств, Джефф Эриксон
• Проект открытых проблем, Задача 7: k-множества