система CC

В вычислительной геометрии система CC или система против часовой стрелки представляет собой троичное отношение $pqr,$ введенное Дональдом Кнутом для моделирования упорядочения по часовой стрелке троек точек в общем положении на евклидовой плоскости . ^[1]

Аксиомы [ править ]

Система CC должна удовлетворять следующим аксиомам для всех различных точек p , q , r , s и t : ^[2]

Циклическая симметрия: если $pqr,$ то $qrp$ .
Антисимметрия: если $pqr$ , то не $prq$ .
Невырожденность: либо $pqr$ , либо $prq$ .
Внутренность: если $tqr$ и $ptr$ и $pqt$ , то $pqr$ .
Транзитивность: если $tsp$ и $tsq$ и $tsr$ , и $tpq$ и $tqr$ , то $tpr$ .

Тройки точек, которые не являются различными, не считаются частью отношения.

Построение из наборов плоских точек [ править ]

Система CC может быть определена из любого набора точек евклидовой плоскости , при этом никакие три точки не лежат на одной прямой, путем включения в отношение тройки $различных$ точек всякий раз, когда тройка перечисляет эти три точки в порядке против часовой стрелки вокруг треугольника, в котором они расположены. форма. Используя декартовы координаты точек, тройка pqr включается в соотношение именно тогда, когда ^[3]

\det \left({\begin{array}{ccc}x_{p}&y_{p}&1\\x_{q}&y_{q}&1\\x_{r}&y_{r}&1\end{array}}\right)>0.

Условие того, что точки находятся в общем положении, эквивалентно требованию, чтобы этот определитель матрицы никогда не был равен нулю для различных точек p , q и r .

Однако не каждая система CC возникает из набора евклидовых точек таким образом. ^[4]

Эквивалентные понятия [ править ]

Системы CC также могут быть определены на основе псевдолинейных схем или сетей сортировки , в которых операции сравнения-обмена сравнивают только соседние пары элементов (как, например, в пузырьковой сортировке ), и каждая система CC может быть определена таким образом. ^[5] Это отношение не является однозначно однозначным, но количество неизоморфных систем CC в n точках, схем псевдолиний с n строками и сортировочных сетей по n значениям находятся в пределах полиномиальных коэффициентов друг от друга. ^[6]

3 существует соответствие два к одному однородными ациклическими ориентированными матроидами ранга Между системами CC и . ^[7] Эти матроиды, в свою очередь, имеют 1-1 соответствие классам топологической эквивалентности псевдолинейных расположений с одной отмеченной клеткой. ^[6]

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

Информации, предоставляемой системой CC, достаточно, чтобы определить понятие выпуклой оболочки в системе CC. Выпуклая оболочка — это набор упорядоченных пар pq обладающий свойством, что для каждой третьей отдельной точки r pqr различных точек , принадлежит системе. Он образует цикл, свойство которого состоит в том, что каждые три точки цикла в одном и том же циклическом порядке принадлежат системе. ^[8] Добавляя точки по одной в систему CC и поддерживая выпуклую оболочку добавленных до сих пор точек в ее циклическом порядке с использованием двоичного дерева поиска , можно построить выпуклую оболочку за время O ( n log n ), сопоставление известных временных границ для алгоритмов выпуклой оболочки для евклидовых точек. ^[9]

Также возможно найти одну вершину выпуклой оболочки, а также комбинаторный эквивалент биссектрисы, проходящей через систему точек, из системы CC за линейное время . Построение крайней вершины позволяет обобщить алгоритм сканирования Грэма для выпуклых оболочек от наборов точек до систем CC с рядом запросов к системе CC, которые соответствуют (с точностью до членов более низкого порядка) количеству сравнений, необходимых для сравнения. сортировка . ^[10]

Комбинаторное перечисление [ править ]

Число неизоморфных систем CC в n точках равно ^[6]^[11]

1, 1, 1, 2, 3, 20, 242, 6405, 316835, 28627261... (последовательность A006246 в OEIS )

Эти числа растут экспоненциально в n ²; ^[12] напротив, число реализуемых систем CC растет экспоненциально только по Θ( n log n ). ^[7]

Точнее, число Cn _n неизоморфных СС-систем в точках не превосходит ^[13]

3^{\binom {n}{2}}.

Кнут более сильно предполагает, что эти числа подчиняются рекурсивному неравенству

C_{n}\leq n2^{n-2}C_{n-1}.

Примечания [ править ]

^ Кнут (1992) .
^ Кнут (1992) , с. 4.
^ Кнут (1992) , с. 3.
^ Кнут (1992) , стр. 25–26.
^ Кнут (1992) , стр. 29–35.
^ Jump up to: Перейти обратно: ^а ^б ^с Кнут (1992) , с. 35.
^ Jump up to: Перейти обратно: ^а ^б Кнут (1992) , с. 40.
^ Кнут (1992) , стр. 45–46.
^ Кнут (1992) , с. 47.
^ Айххольцер, Мильцов и Пильц (2013) .
^ Бейгельцимер и Радзишовский (2002) .
^ Кнут (1992) , с. 37.
^ Кнут (1992) , с. 39.

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

Айххольцер, Освин; Мильцов, Тильманн; Пильц, Александр (2013), «Поиск крайних точек и половинных ребер в абстрактных типах порядка», Computational Geometry , 46 (8): 970–978, doi : 10.1016/j.comgeo.2013.05.001 , MR 3061458 , PMC 3688538 , ПМИД 24092953 .
Бейгельзимер, Алина; Радзишовский, Станислав (2002), «О расположении половинных линий», Discrete Mathematics , 257 (2–3): 267–283, doi : 10.1016/S0012-365X(02)00430-2 , MR 1935728 .
Кнут, Дональд Э. (1992), Аксиомы и оболочки , Конспекты лекций по информатике, том. 606, Гейдельберг: Springer-Verlag, стр. ix+109, doi : 10.1007/3-540-55611-7 , ISBN 3-540-55611-7 , MR 1226891 , S2CID 5452191 , заархивировано из оригинала 20 июня 2017 года , получено 5 мая 2011 года .

[FOOTNOTEKnuth1992-1] Кнут (1992) .

[FOOTNOTEKnuth19924-2] Кнут (1992) , с. 4.

[FOOTNOTEKnuth19923-3] Кнут (1992) , с. 3.

[FOOTNOTEKnuth199225–26-4] Кнут (1992) , стр. 25–26.

[FOOTNOTEKnuth199229–35-5] Кнут (1992) , стр. 29–35.

[FOOTNOTEKnuth199235-6] Jump up to: Перейти обратно: ^а ^б ^с Кнут (1992) , с. 35.

[FOOTNOTEKnuth199240-7] Jump up to: Перейти обратно: ^а ^б Кнут (1992) , с. 40.

[FOOTNOTEKnuth199245–46-8] Кнут (1992) , стр. 45–46.

[FOOTNOTEKnuth199247-9] Кнут (1992) , с. 47.

[FOOTNOTEAichholzerMiltzowPilz2013-10] Айххольцер, Мильцов и Пильц (2013) .

[FOOTNOTEBeygelzimerRadziszowski2002-11] Бейгельцимер и Радзишовский (2002) .

[FOOTNOTEKnuth199237-12] Кнут (1992) , с. 37.

[FOOTNOTEKnuth199239-13] Кнут (1992) , с. 39.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]