Sistema CC - CC system

En geometría computacional , un sistema CC o sistema en sentido antihorario es una relación ternaria pqr introducida por Donald Knuth para modelar el orden en el sentido de las agujas del reloj de triples de puntos en posición general en el plano euclidiano .

Axiomas

Se requiere un sistema CC para satisfacer los siguientes axiomas, para todos los puntos distintos p , q , r , s y t :

1. La simetría cíclica: Si PQR continuación QRP .
2. Antisimetría: Si pqr entonces no prq .
3. No degeneración: pqr o prq .
4. Interioridad: si tqr y ptr y pqt , entonces pqr .
5. Transitividad: si tsp y tsq y tsr , y tpq y tqr , entonces tpr .

Los triples de puntos que no son distintos no se consideran parte de la relación.

Construcción a partir de conjuntos de puntos planos

Un sistema CC puede definirse a partir de cualquier conjunto de puntos en el plano euclidiano , sin que tres de los puntos sean colineales, al incluir en la relación un triple pqr de puntos distintos siempre que el triple enumere estos tres puntos en orden antihorario alrededor del triángulo en el que se encuentran. formulario. Usando las coordenadas cartesianas de los puntos, el triple pqr se incluye en la relación exactamente cuando

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

La condición de que los puntos están en posición general es equivalente a la exigencia de que esta matriz determinante nunca es cero para distintos puntos p , q , y r .

Sin embargo, no todos los sistemas CC provienen de un punto euclidiano establecido de esta manera.

Nociones equivalentes

Los sistemas CC también se pueden definir a partir de arreglos de pseudolínea o de redes de clasificación en las que las operaciones de comparación e intercambio solo comparan pares de elementos adyacentes (como en, por ejemplo, clasificación de burbujas ), y cada sistema CC se puede definir de esta manera. Esta relación no es de uno a uno, pero el número de sistemas CC no isomórficos en n puntos, de arreglos de pseudolina con n líneas y de redes de clasificación en n valores, están dentro de factores polinomiales entre sí.

Existe una correspondencia de dos a uno entre los sistemas CC y las matroides orientadas acíclicas uniformes de rango 3. Estas matroides a su vez tienen una correspondencia 1-1 con las clases de equivalencia topológica de arreglos de pseudolina con una celda marcada.

Aplicaciones algorítmicas

La información proporcionada por un sistema CC es suficiente para definir una noción de casco convexo dentro de un sistema CC. El casco convexo 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. Añadiendo puntos uno a la vez a un sistema CC, y manteniendo el casco convexo de los puntos añadidos hasta ahora en su orden cíclico usando un árbol de búsqueda binario , es posible construir el casco convexo en el tiempo O ( n  log  n ), coincidir con los límites de tiempo conocidos para los algoritmos de casco convexo para puntos euclidianos.

También es posible encontrar un único vértice de casco convexo, 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 generalizar el algoritmo de escaneo de Graham para cascos convexos de conjuntos de puntos a sistemas CC, con una serie de consultas al sistema CC que coinciden (dentro de términos de orden inferior) con el número de comparaciones necesarias en comparación. clasificación .

Enumeración combinatoria

El número de sistemas CC no isomórficos en n puntos es

1, 1, 1, 2, 3, 20, 242, 6405, 316835, 28627261 ... (secuencia A006246 en la OEIS )

Estos números crecen exponencialmente en n ² ; en contraste, el número de sistemas CC realizables crece exponencialmente solo en Θ ( n  log  n ).

Más precisamente, el número C _n de sistemas CC no isomórficos en n puntos es como máximo

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

Knuth conjetura con más fuerza que estos números obedecen a la desigualdad recursiva

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

Notas

Referencias

• Aichholzer, Oswin; Miltzow, Tillmann; Pilz, Alexander (2013), "Búsqueda de bordes extremos y reducidos a la mitad en tipos de orden abstracto", Geometría computacional , 46 (8): 970–978, doi : 10.1016 / j.comgeo.2013.05.001 , MR  3061458 , PMC  3688538 , PMID  24092953.
• Beygelzimer, Alina; Radziszowski, Stanisław (2002), "Sobre arreglos de líneas a la mitad", Discrete Mathematics , 257 (2-3): 267-283, doi : 10.1016 / S0012-365X (02) 00430-2 , MR  1935728.
• Knuth, Donald E. (1992), Axiomas y cascos , Lecture Notes in Computer Science, 606 , Heidelberg: Springer-Verlag, págs. Ix + 109, doi : 10.1007 / 3-540-55611-7 , ISBN 3-540-55611-7, MR  1226891 , consultado el 5 de mayo de 2011.