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

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

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

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

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

Нерешенная проблема в математике:

Какое наибольшее возможное количество строк деления пополам для набора

{displaystyle n}

точки в плоскости?

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

При анализе геометрических алгоритмов важно ограничить количество 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, ... есть

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

Также доказаны границы для числа ≤k-множества, где a ≤k-сет - это j-установка для некоторых j ≤ k. В двух измерениях максимальное количество ≤k-установки точно нк,^[5] пока в d размеры граница ${displaystyle O (n ^ {lfloor d / 2floor} k ^ {lceil d / 2ceil})}$ .^[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).

внешняя ссылка

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

[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] Гусфилд (1980); Ishii et al. (1981); Като и Ибараки (1983); Хассин и Тамир (1989); Fernández-Baca et al. (1996); Чан (2005c).

[9] Эпштейн (1998).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]