K-набор (геометрия) - K-set (geometry)
В дискретная геометрия, а k-множество конечного точечного множества S в Евклидова плоскость это подмножество из k элементы S которые можно строго отделить от остальных точек линия. В более общем плане в Евклидово пространство высших измерений, k-множество конечных точек - это подмножество k элементы, которые можно отделить от остальных точек гиперплоскость. В частности, когда k = п/ 2 (где п это размер S), линия или гиперплоскость, разделяющая k-установлен из остальной части S это линия вдвое или же половина плоскости.
K-множества связаны проективная двойственность к k-уровни в расположение линий; в k-уровень в расположении п прямые на плоскости - это кривая, состоящая из точек, лежащих на одной из прямых и имеющих ровно k линии под ними. Дискретные и вычислительные геометры также изучали уровни в расположении более общих типов кривых и поверхностей.[1]
Комбинаторные оценки
 | Нерешенная проблема в математике: Какое наибольшее возможное количество строк деления пополам для набора точки в плоскости? (больше нерешенных задач по математике) |
При анализе геометрических алгоритмов важно ограничить количество k-наборы плоского набора точек,[2] или эквивалентно количество k-уровни расположения плоских линий, проблема, впервые изученная Ловас (1971) и Erds и другие. (1973). Самая известная верхняя оценка этой проблемы - О(нк1/3), как показал Тамал Дей (1998) с использованием пересечение числового неравенства Аджтай, Chvátal, Новорожденный и Семереди. Однако самая известная нижняя граница далека от верхней границы Дея: это Ω (п ехр (c (бревноk)1/2)) для некоторой постоянной c, как показал Тот (2001).
В трех измерениях наилучшая известная верхняя граница О(нк3/2), а наилучшая известная нижняя граница - Ω (нк ехр (c (бревноk)1/2)).[3]Для точек в трех измерениях, находящихся в выпуклое положение, то есть являются вершинами некоторого выпуклого многогранника, количество k-множеств равно Θ ((н-к) к), что следует из аргументов, используемых для оценки сложности диаграмм Вороного k-го порядка.[4]
На случай, когда k = п/ 2 (деление пополам), максимальное количество комбинаторно различных прямых, проходящих через две точки S которые делят пополам оставшиеся точки, когда k = 1, 2, ... есть
Также доказаны границы для числа ≤k-множества, где a ≤k-сет - это j-установка для некоторых j ≤ k. В двух измерениях максимальное количество ≤k-установки точно нк,[5] пока в d размеры граница .[6]
Алгоритмы построения
Эдельсбруннер и Вельцль (1986) впервые изучили проблему построения всех k-множества входного набора точек или двойного построения k-уровень расположения. В k-уровневую версию их алгоритма можно рассматривать как развертка алгоритм, который строит уровень слева направо. Рассмотрено с точки зрения k-множества наборов точек, их алгоритм поддерживает динамическая выпуклая оболочка для точек по обе стороны от разделительной линии, многократно находит битангентный этих двух корпусов, и перемещает каждую из двух точек касания к противоположному корпусу. Чан (1999) рассматривает последующие результаты по этой проблеме и показывает, что она может быть решена за время, пропорциональное Дею. О(нк1/3) оценка сложности k-уровень.
Агарвал и Матушек описывать алгоритмы эффективного построения примерного уровня; то есть кривая, проходящая между (k - d) -уровень и (k + d) -уровень для некоторого малого параметра приближения d. Они показывают, что можно найти такое приближение, состоящее из ряда отрезков прямых, зависящих только от п/d а не на п или же k.[7]
Обобщения матроидов
Планарный k-уровневая задача может быть обобщена на задачу параметрической оптимизации в матроид: каждому дается матроид, в котором каждый элемент взвешивается линейной функцией параметра λ, и он должен найти базис минимального веса матроида для каждого возможного значения λ. Если изобразить весовые функции в виде линий на плоскости, k-уровень расположения этих графиков в зависимости от λ веса наибольшего элемента в оптимальном базисе в униформа матроид, и Дей показал, что его О(нк1/3) оценка сложности k-уровень можно обобщить, чтобы подсчитать количество различных оптимальных оснований любого матроида с п элементы и ранг k.
Например, тот же О(нк1/3) верхняя оценка верна для подсчета количества различных минимальные остовные деревья формируется в виде графика с п края и k вершины, когда вес ребер изменяется линейно с параметром λ. Эта параметрическая задача минимального остовного дерева изучалась различными авторами и может использоваться для решения других задач оптимизации бикритериального остовного дерева.[8]
Однако наиболее известной нижней оценкой для параметрической задачи о минимальном остовном дереве является Ω (п α (k)), где α - обратная функция Аккермана, даже более слабая оценка, чем оценка для k-установить проблему. Для более общих матроидов Dey's О(нк1/3) верхняя граница имеет соответствующую нижнюю границу.[9]
Примечания
- ^ Agarwal et al. (1997); Чан (2003; 2005а, б).
- ^ Шазель и Препарата (1986); Cole et al. (1987); Эдельсбруннер и Вельцль (1986).
- ^ Шарир и др. (2001).
- ^ Ли (1982); Кларксон и Шор (1989).
- ^ Алон и Дьёри (1986).
- ^ Кларксон и Шор (1989).
- ^ Агарвал (1990); Матушек (1990,1991).
- ^ Гусфилд (1980); Ishii et al. (1981); Като и Ибараки (1983); Хассин и Тамир (1989); Fernández-Baca et al. (1996); Чан (2005c).
- ^ Эпштейн (1998).
Рекомендации
- Агарвал, П. К. (1990). «Разбиение линий I: эффективный детерминированный алгоритм». Дискретная и вычислительная геометрия. 5 (1): 449–483. Дои:10.1007 / BF02187805.
- Агарвал, П. К.; Аронов, Б.; Шарир, М. (1997). «На уровнях в расположении линий, отрезков, плоскостей и треугольников». Proc. 13-й ежегодный симпозиум по вычислительной геометрии. С. 30–38.
- Алон, Н.; Дьёри, Э. (1986). «Число малых полупространств конечного множества точек на плоскости». Журнал комбинаторной теории, серия А. 41: 154–157. Дои:10.1016/0097-3165(86)90122-6.
- Чан, Т. (1999). «Замечания об алгоритмах k-го уровня в плоскости». Архивировано из оригинал на 2010-11-04. Цитировать журнал требует
| журнал =(помощь) - Чан, Т. (2003). «По уровням в расположении кривых». Дискретная и вычислительная геометрия. 29 (3): 375–393. Дои:10.1007 / s00454-002-2840-2.
- Чан, Т. (2005a). «На уровнях в расположении кривых, II: простое неравенство и его последствия». Дискретная и вычислительная геометрия. 34: 11–24. Дои:10.1007 / s00454-005-1165-3.
- Чан, Т. (2005b). «На уровнях в расположении поверхностей в трех измерениях». Материалы 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. С. 232–240.
- Чан, Т. (2005c). «Поиск самого короткого края узкого места в параметрическом минимальном остовном дереве». Материалы 16-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. С. 232–240.
- Шазель, Б.; Препарата, Ф. (1986). "Поиск по дальности полупространства: алгоритмическое применение k-комплекты ". Дискретная и вычислительная геометрия. 1 (1): 83–93. Дои:10.1007 / BF02187685. МИСТЕР 0824110.
- Кларксон, К.; Шор, П. (1989). «Применение случайной выборки, II». Дискретная и вычислительная геометрия. 4: 387–421. Дои:10.1007 / BF02187740.
- Cole, R .; Шарир, М.; Яп, К. К. (1987). "На k-корпуса и связанные с ним проблемы ». SIAM Журнал по вычислениям. 16 (1): 61–77. Дои:10.1137/0216005. МИСТЕР 0873250.
- Дей, Т.К. (1998). "Улучшены границы для плоских k-наборы и связанные с ними проблемы ». Дискретная и вычислительная геометрия. 19 (3): 373–382. Дои:10.1007 / PL00009354. МИСТЕР 1608878.
- Эдельсбруннер, Х.; Вельцль, Э. (1986). «Конструирование ремней в двухмерном расположении с приложениями». SIAM Журнал по вычислениям. 15 (1): 271–284. Дои:10.1137/0215019.
- Эппштейн, Д. (1998). «Геометрические нижние границы для параметрической оптимизации матроидов» (PDF). Дискретная и вычислительная геометрия. 20 (4): 463–476. Дои:10.1007 / PL00009396.
- Эрдеш, П.; Ловас, Л.; Simmons, A .; Штраус, Э. (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. Калифорнийский университет в Беркли. Цитировать журнал требует
| журнал =(помощь) - Hassin, R .; Тамир, А. (1989). «Максимизация классов двухпараметрических объективов над матроидами». Математика. Опер. Res. 14 (2): 362–375. Дои:10.1287 / moor.14.2.362.
- Ishii, H .; Shiode, S .; Нисида, Т. (1981). «Проблема стохастического остовного дерева». Дискретная прикладная математика. 3 (4): 263–273. Дои:10.1016 / 0166-218X (81) 90004-4.
- Katoh, N .; Ибараки, Т. (1983). «Об общем количестве стержней, необходимых для некоторых задач параметрической комбинаторной оптимизации». Рабочий документ 71. Inst. Экон. Res., Kobe Univ. торговли. Цитировать журнал требует
| журнал =(помощь) - Ли, Дер-Цай (1982). «О k-ближних диаграммах Вороного на плоскости». Транзакции IEEE на компьютерах. 31 (6): 478–487. Дои: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. Дои:10.1007 / BF02187804. МИСТЕР 1064574.
- Матушек, Я. (1991). «Примерные уровни расположения линий». SIAM Журнал по вычислениям. 20 (2): 222–227. Дои:10.1137/0220013.
- Шарир, М.; Смородинский, С .; Тардос, Г. (2001). "Улучшенная граница для k-наборы в трех измерениях ». Дискретная и вычислительная геометрия. 26: 195–204. Дои:10.1007 / s00454-001-0005-3.
- Тот, Г. (2001). "Наборы точек со многими k-комплекты ". Дискретная и вычислительная геометрия. 26 (2): 187–194. Дои:10.1007 / s004540010022.