Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Набор из шести точек (красный), его шесть 2-наборов (наборы точек, содержащихся в синих овалах) и линий, отделяющих каждый k-набор от остальных точек (пунктирный черный).

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

K -множества связаны проективной двойственностью с k -уровнями в расположении строк ; к -уровню в расположении п линий в плоскости является кривым , состоящими из точек , которые лежат на одной из линий и точно K строки ниже них. Дискретные и вычислительные геометры также изучали уровни в расположении более общих типов кривых и поверхностей. [1]

Комбинаторные границы [ править ]

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

Какое максимально возможное количество линий, разделенных пополам, для набора точек на плоскости?

(больше нерешенных задач по математике)

При анализе геометрических алгоритмов важно ограничить количество k -множеств плоского набора точек [2] или, что то же самое, количество k -уровней плоского расположения линий, проблема, впервые изученная Lovász (1971). и Erdős et al. (1973). Самая известная верхняя граница для этой проблемы - O ( nk 1/3 ), как было показано Tamal Dey (1998) с использованием неравенства числа пересечений Ajtai, Chvátal , Newborn и Szemerédi . Однако наиболее известная нижняя граница далека от верхней границы Дея: это Ω ( n exp ( c(log k ) 1/2 )) для некоторой константы c , как показано Toth (2001).

В трех измерениях наилучшая известная верхняя граница - O ( nk 3/2 ), а наилучшая известная нижняя граница - Ω ( nk exp ( c (log k ) 1/2 )). [3] Для точек в трех измерениях, которые находятся в выпуклом положении , то есть являются вершинами некоторого выпуклого многогранника, количество k-множеств равно Θ ( (nk) k ), что следует из аргументов, используемых для ограничения сложности Диаграммы Вороного k-го порядка. [4]

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

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

Также были доказаны границы для числа ≤ k -множеств, где ≤ k -множество является j -множеством для некоторого j ≤ k . В двух измерениях максимальное количество ≤ k -множеств равно nk , [5] в то время как в d измерениях граница равна . [6]

Алгоритмы построения [ править ]

Эдельсбруннер и Велцл (1986) впервые изучили проблему построения всех k -множеств входного набора точек или двойного построения k -уровня компоновки. К версии -уровень их алгоритма можно рассматривать как развертки плоскости алгоритм , который строит уровень в левой направо порядке. Рассматриваемый с точки зрения k -множеств наборов точек, их алгоритм поддерживает динамическую выпуклую оболочку для точек на каждой стороне разделяющей линии, неоднократно находит биткасательнуюэтих двух корпусов и перемещает каждую из двух точек касания к противоположному корпусу. Чан (1999) рассматривает последующие результаты по этой проблеме и показывает, что ее можно решить за время, пропорциональное оценке Дея сложности k -уровня O ( nk 1/3 ) .

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

Обобщения Matroid [ править ]

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

Например, та же самая верхняя граница O ( nk 1/3 ) верна для подсчета количества различных минимальных остовных деревьев, сформированных в графе с n ребрами и k вершинами, когда вес ребер изменяется линейно с параметром λ. Эта параметрическая задача минимального остовного дерева изучалась различными авторами и может использоваться для решения других задач оптимизации бикритериального остовного дерева. [8]

Однако наиболее известной нижней оценкой для параметрической задачи о минимальном остовном дереве является Ω ( n α ( k )), где α - обратная функция Аккермана , даже более слабая оценка, чем для задачи о k -множестве. Для более общих матроидов верхняя граница Дея O ( nk 1/3 ) имеет соответствующую нижнюю границу. [9]

Заметки [ править ]

  1. ^ Agarwal et al. (1997); Чан (2003; 2005а, б).
  2. ^ Шазель и Препарата (1986); Cole et al. (1987); Эдельсбруннер и Вельцль (1986).
  3. ^ Шарир и др. (2001).
  4. ^ Ли (1982); Кларксон и Шор (1989).
  5. ↑ Алон и Дьёри (1986).
  6. ^ Кларксон и Шор (1989).
  7. ^ Агарвал (1990); Матушек (1990,1991).
  8. ^ Gusfield (1980); Ishii et al. (1981); Като и Ибараки (1983); Хассин и Тамир (1989); Fernández-Baca et al. (1996); Чан (2005c).
  9. ^ Эпштайна (1998).

Ссылки [ править ]

  • Агарвал, ПК (1990). «Разбиение линий I: эффективный детерминированный алгоритм» . Дискретная и вычислительная геометрия . 5 (1): 449–483. DOI : 10.1007 / BF02187805 .
  • Agarwal, PK ; Аронов, Б .; Шарир, М. (1997). «На уровнях в расположении линий, отрезков, плоскостей и треугольников». Proc. 13-й ежегодный симпозиум по вычислительной геометрии . С. 30–38.
  • Алон, Н .; Дьёри, Э. (1986). «Число малых полупространств конечного множества точек на плоскости» . Журнал комбинаторной теории, Серия А . 41 : 154–157. DOI : 10.1016 / 0097-3165 (86) 90122-6 .
  • Чан, TM (1999). «Замечания об алгоритмах k-го уровня в плоскости» . Архивировано из оригинала на 2010-11-04. Цитировать журнал требует |journal=( помощь )
  • Чан, TM (2003). «По уровням в расположении кривых» . Дискретная и вычислительная геометрия . 29 (3): 375–393. DOI : 10.1007 / s00454-002-2840-2 .
  • Чан, TM (2005a). «По уровням в расположении кривых, II: простое неравенство и его последствия» . Дискретная и вычислительная геометрия . 34 : 11–24. DOI : 10.1007 / s00454-005-1165-3 .
  • Чан, TM (2005b). «По уровням в расположении поверхностей в трех измерениях» . Труды 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 232–240.
  • Чан, TM (2005c). «Нахождение самого короткого края узкого места в параметрическом минимальном остовном дереве» . Труды 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 232–240.
  • Chazelle, B .; Препарата, ФП (1986). «Поиск по дальности полупространства: алгоритмическое применение k -множеств» . Дискретная и вычислительная геометрия . 1 (1): 83–93. DOI : 10.1007 / BF02187685 . Руководство по ремонту  0824110 .
  • Кларксон, KL ; Шор, П. (1989). «Приложения случайной выборки, II» . Дискретная и вычислительная геометрия . 4 : 387–421. DOI : 10.1007 / BF02187740 .
  • Cole, R .; Шарир, М .; Яп, СК (1987). «О k- корпусах и связанных с ними проблемах». SIAM Journal on Computing . 16 (1): 61–77. DOI : 10.1137 / 0216005 . Руководство по ремонту  0873250 .
  • Дей, Т.К. (1998). «Улучшенные оценки планарных k -множеств и связанных с ними задач» . Дискретная и вычислительная геометрия . 19 (3): 373–382. DOI : 10.1007 / PL00009354 . Руководство по ремонту  1608878 .
  • Эдельсбруннер, Х .; Велцль, Э. (1986). «Конструирование ремней в двухмерном расположении с приложениями». SIAM Journal on Computing . 15 (1): 271–284. DOI : 10,1137 / 0215019 .
  • Эппштейн, Д. (1998). «Геометрические нижние границы для параметрической оптимизации матроидов» (PDF) . Дискретная и вычислительная геометрия . 20 (4): 463–476. DOI : 10.1007 / PL00009396 .
  • Erdős, P .; Ловас, Л .; Simmons, A .; Straus, EG (1973). «Графики разрезов плоских множеств точек». Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) . Амстердам: Северная Голландия. С. 139–149. Руководство по ремонту  0363986 .
  • Fernández-Baca, D .; Slutzki, G .; Эппштейн, Д. (1996). «Использование разрежения для параметрических задач минимального остовного дерева». Северный журнал вычислительной техники . 3 (4): 352–366.
  • Гусфилд, Д. (1980). «Анализ чувствительности для комбинаторной оптимизации». Tech. Представитель UCB / ERL M80 / 22. Калифорнийский университет в Беркли. Цитировать журнал требует |journal=( помощь )
  • Hassin, R .; Тамир, А. (1989). «Максимизация классов двухпараметрических объективов над матроидами». Математика. Опер. Res . 14 (2): 362–375. DOI : 10.1287 / moor.14.2.362 .
  • Ishii, H .; Shiode, S .; Нисида, Т. (1981). «Проблема стохастического остовного дерева». Дискретная прикладная математика . 3 (4): 263–273. DOI : 10.1016 / 0166-218X (81) 90004-4 .
  • Katoh, N .; Ибараки, Т. (1983). «Об общем количестве стержней, необходимых для некоторых задач параметрической комбинаторной оптимизации». Рабочий документ 71. Inst. Экон. Res., Kobe Univ. торговли. Цитировать журнал требует |journal=( помощь )
  • Ли, Дер-Цай (1982). "О k-ближних диаграммах Вороного на плоскости". Транзакции IEEE на компьютерах . 31 (6): 478–487. DOI : 10.1109 / TC.1982.1676031 .
  • Ловас, Л. (1971). «О количестве линий вдвое». Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica . 14 : 107–108.
  • Матушек, Дж. (1990). «Построение ε-сетей» . Дискретная и вычислительная геометрия . 5 (5): 427–448. DOI : 10.1007 / BF02187804 . Руководство по ремонту  1064574 .
  • Матушек, J. (1991). «Примерные уровни расположения линий». SIAM Journal on Computing . 20 (2): 222–227. DOI : 10.1137 / 0220013 .
  • Шарир, М .; Смородинский, С .; Тардос, Г. (2001). «Улучшенная оценка k -множеств в трех измерениях» . Дискретная и вычислительная геометрия . 26 : 195–204. DOI : 10.1007 / s00454-001-0005-3 .
  • Тот, Г. (2001). «Наборы точек со многими k -множествами» . Дискретная и вычислительная геометрия . 26 (2): 187–194. DOI : 10.1007 / s004540010022 .

Внешние ссылки [ править ]

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