Система CC
-
Система CC в вычислительной геометрии
- Система CC (против часовой стрелки) — троичное соотношение pqr, введенное Дональдом Кнутом.
- Моделирует упорядочение троек точек в общем положении на евклидовой плоскости.
-
Аксиомы системы CC
- Циклическая симметрия: pqr -> qrp.
- Антисимметрия: pqr -> не prq.
- Невырожденность: либо pqr, либо prq.
- Внутренний уровень: tqr, ptr и pqt -> pqr.
- Транзитивность: tsp, tsq и tsr, tpq и tqr -> tpr.
-
Построение из плоских наборов точек
- Система CC определяется из набора точек на евклидовой плоскости.
- Тройной pqr включается, если точки перечисляются против часовой стрелки вокруг треугольника.
- Условие общего положения эквивалентно матричному определителю, не равному нулю.
-
Эквивалентные понятия
- Системы CC могут быть определены через псевдолинейные схемы или сети сортировки.
- Существует соответствие между системами CC и однородными ациклически ориентированными матроидами ранга 3.
-
Алгоритмические приложения
- Система CC позволяет определить выпуклую оболочку.
- Выпуклая оболочка — множество упорядоченных пар точек, для которых pqr принадлежит системе.
- Построение выпуклой оболочки за O(n log n) с использованием бинарного дерева поиска.
- Поиск единственной вершины выпуклой оболочки и комбинаторного эквивалента линии за линейное время.
-
Комбинаторное перечисление
- Число неизоморфных систем CC в n точках экспоненциально растет в n2.
- Число реализуемых систем CC растет экспоненциально в Θ(n log n).
- Кнут предполагает рекурсивное неравенство для числа систем CC.