En geometría computacional , un sistema CC o sistema antihorario es una relación ternaria pqr introducida por Donald Knuth para modelar el ordenamiento en el sentido de las agujas del reloj de triples de puntos en posición general en el plano euclidiano . [1]
Se requiere que un sistema CC satisfaga los siguientes axiomas, para todos los puntos distintos p , q , r , s y t : [2]
Los triples de puntos que no son distintos no se consideran parte de la relación.
Un sistema CC puede definirse a partir de cualquier conjunto de puntos en el plano euclidiano , sin tres de los puntos colineales, incluyendo en la relación una triple pqr de puntos distintos siempre que la triple enumere estos tres puntos en orden antihorario alrededor del triángulo que forman. Usando las coordenadas cartesianas de los puntos, la triple pqr se incluye en la relación exactamente cuando [3]
La condición de que los puntos estén en posición general es equivalente al requisito de que este determinante de la matriz nunca sea cero para los puntos distintos p , q y r .
Sin embargo, no todos los sistemas CC provienen de un punto euclidiano establecido de esta manera. [4]
Los sistemas CC también pueden definirse a partir de arreglos pseudolineales , o a partir de redes de ordenamiento en las que las operaciones de comparación-intercambio solo comparan pares adyacentes de elementos (como por ejemplo en el ordenamiento de burbuja ), y cada sistema CC puede definirse de esta manera. [5] Esta relación no es biunívoca, pero los números de sistemas CC no isomorfos en n puntos, de arreglos pseudolineales con n líneas, y de redes de ordenamiento en n valores, están dentro de factores polinomiales entre sí. [6]
Existe una correspondencia dos a uno entre los sistemas CC y los matroides orientados acíclicos uniformes de rango 3. [7] Estos matroides a su vez tienen una correspondencia 1 a 1 con las clases de equivalencia topológica de arreglos de pseudolíneas con una celda marcada. [6]
La información proporcionada por un sistema CC es suficiente para definir una noción de envoltura convexa dentro de un sistema CC. La envoltura convexa es el conjunto de pares ordenados pq de puntos distintos con la propiedad de que, por cada tercer punto distinto r , pqr pertenece al sistema. Forma un ciclo, con la propiedad de que cada tres puntos del ciclo, en el mismo orden cíclico, pertenecen al sistema. [8] Al agregar puntos uno a la vez a un sistema CC, y mantener la envoltura convexa de los puntos agregados hasta ahora en su orden cíclico utilizando un árbol de búsqueda binaria , es posible construir la envoltura convexa en tiempo O ( n log n ), coincidiendo con los límites de tiempo conocidos para algoritmos de envoltura convexa para puntos euclidianos. [9]
También es posible encontrar un único vértice de envoltura convexa, así como el equivalente combinatorio de una línea bisectriz a través de un sistema de puntos, a partir de un sistema CC en tiempo lineal . La construcción de un vértice extremo permite que el algoritmo de escaneo de Graham para envolturas convexas se generalice a partir de conjuntos de puntos a sistemas CC, con una cantidad de consultas al sistema CC que coincida (dentro de términos de orden inferior) con la cantidad de comparaciones necesarias en la clasificación por comparación . [10]
El número de sistemas CC no isomorfos en n puntos es [6] [11]
Estos números crecen exponencialmente en n 2 ; [12] en contraste, el número de sistemas CC realizables crece exponencialmente solo en Θ( n log n ). [7]
Más precisamente, el número C n de sistemas CC no isomorfos en n puntos es como máximo [13]
Knuth conjetura con mayor fuerza que estos números obedecen a la desigualdad recursiva
