Loading article…
計算幾何学において、CCシステムまたは反時計回りシステムは、ユークリッド平面上の一般位置にある3つの点の時計回りの順序をモデル化するためにドナルド・クヌースによって導入された3項関係pqrである。[ 1 ]
CC システムは、すべての異なる点p、q、r、s、tに対して、次の公理を満たす必要があります。[ 2 ]
互いに異なる点の3つ組は、関係の一部とはみなされません。
CC システムは、ユークリッド平面上の任意の点の集合から定義できます。ただし、どの 3 つの点も共線ではありません。この定義では、異なる点の 3 つpqr を関係に含めることで定義できます。この 3 つが、それらが形成する三角形の周りを反時計回りの順序でリストしている場合にのみ定義できます。点のデカルト座標を使用すると、3 つpqr は、まさに[ 3 ]のときに関係に含まれます。
点が一般の位置にあるという条件は、異なる点p、q、rに対してこの行列式がゼロにならないという要件と同等である。
しかし、すべてのCCシステムがこのようにユークリッド点集合から得られるわけではない。[ 4 ]
CC システムは擬似線配置、または比較交換操作が隣接する要素のペアのみを比較するソート ネットワーク(例えばバブル ソートなど) から定義することもでき、すべての CC システムはこのように定義できます。[ 5 ]この関係は 1 対 1 ではありませんが、 n点上の非同型 CC システムの数、 n本の線を持つ擬似線配置の数、およびn値上のソート ネットワークの数は、互いに多項式因子の範囲内です。[ 6 ]
CCシステムとランク3の一様非巡回向き付けマトロイドの間には2対1の対応関係が存在する。[ 7 ]これらのマトロイドは、1つのマーク付きセルを持つ擬似線配置の位相的同値類と1対1の対応関係を持つ。[ 6 ]
CCシステムによって提供される情報は、 CCシステム内の凸包の概念を定義するのに十分である。凸包は、異なる点の順序対pqの集合であり、3番目の異なる点rに対して、pqrがシステムに属するという性質を持つ。これはサイクルを形成し、サイクルの3つの点はすべて同じ循環順序でシステムに属するという性質を持つ。[ 8 ] CCシステムに点を1つずつ追加し、これまでに追加された点の凸包を二分探索木を使用して循環順序で維持することにより、ユークリッド点の凸包アルゴリズムの既知の時間制限に一致するO ( n log n )の時間で凸包を構築することができる。[ 9 ]
線形時間で、CC システムから単一の凸包頂点、および点のシステムを二等分する線の組み合わせ的等価物を見つけることも可能である。極値頂点の構築により、凸包に対するGraham スキャンアルゴリズムを点集合から CC システムへ一般化することができ、比較ソートに必要な比較回数と (低次の項の範囲内で) 一致する CC システムへのクエリ数で済む。[ 10 ]
n点上の非同型 CC システムの数は[ 6 ] [ 11 ]です。
これらの数はn 2に対して指数関数的に増加する。[ 12 ]対照的に、実現可能な CC システムの数は Θ( n log n ) に対してのみ指数関数的に増加する。[ 7 ]
より正確には、 n点上の非同型 CC システムのC nの数は最大で[ 13 ]です。
クヌースは、これらの数値が再帰的不等式に従うとより強く推測している。
