CC system
Template:Short description In computational geometry, a CC system or counterclockwise system is a ternary relation Template:Math introduced by Donald Knuth to model the clockwise ordering of triples of points in general position in the Euclidean plane.Template:Sfnp
Axioms
A CC system is required to satisfy the following axioms, for all distinct points p, q, r, s, and t:Template:Sfnp
- Cyclic symmetry: If Template:Math then Template:Math.
- Antisymmetry: If Template:Math then not Template:Math.
- Nondegeneracy: Either Template:Math or Template:Math.
- Interiority: If Template:Math and Template:Math and Template:Math, then Template:Math.
- Transitivity: If Template:Math and Template:Math and Template:Math, and Template:Math and Template:Math, then Template:Math.
Triples of points that are not distinct are not considered as part of the relation.
Construction from planar point sets
A CC system may be defined from any set of points in the Euclidean plane, with no three of the points collinear, by including in the relation a triple Template:Math of distinct points whenever the triple lists these three points in counterclockwise order around the triangle that they form. Using the Cartesian coordinates of the points, the triple pqr is included in the relation exactly whenTemplate:Sfnp
The condition that the points are in general position is equivalent to the requirement that this matrix determinant is never zero for distinct points p, q, and r.
However, not every CC system comes from a Euclidean point set in this way.Template:Sfnp
Equivalent notions
CC systems can also be defined from pseudoline arrangements, or from sorting networks in which the compare-exchange operations only compare adjacent pairs of elements (as in for instance bubble sort), and every CC system can be defined in this way.Template:Sfnp This relation is not one-to-one, but the numbers of nonisomorphic CC systems on n points, of pseudoline arrangements with n lines, and of sorting networks on n values, are within polynomial factors of each other.Template:Sfnp
There exists a two-to-one correspondence between CC systems and uniform acyclic oriented matroids of rank 3.Template:Sfnp These matroids in turn have a 1-1 correspondence to topological equivalence classes of pseudoline arrangements with one marked cell.Template:Sfnp
Algorithmic applications
The information given by a CC system is sufficient to define a notion of a convex hull within a CC system. The convex hull is the set of ordered pairs pq of distinct points with the property that, for every third distinct point r, pqr belongs to the system. It forms a cycle, with the property that every three points of the cycle, in the same cyclic order, belong to the system.Template:Sfnp By adding points one at a time to a CC system, and maintaining the convex hull of the points added so far in its cyclic order using a binary search tree, it is possible to construct the convex hull in time O(n log n), matching the known time bounds for convex hull algorithms for Euclidean points.Template:Sfnp
It is also possible to find a single convex hull vertex, as well as the combinatorial equivalent of a bisecting line through a system of points, from a CC system in linear time. The construction of an extreme vertex allows the Graham scan algorithm for convex hulls to be generalized from point sets to CC systems, with a number of queries to the CC system that matches (to within lower-order terms) the number of comparisons needed in comparison sorting.Template:Sfnp
Combinatorial enumeration
The number of non-isomorphic CC systems on n points isTemplate:SfnpTemplate:Sfnp
- 1, 1, 1, 2, 3, 20, 242, 6405, 316835, 28627261 ... Template:OEIS
These numbers grow exponentially in n2;Template:Sfnp in contrast, the number of realizable CC systems grows exponentially only in Θ(n log n).Template:Sfnp
More precisely, the number Cn of non-isomorphic CC systems on n points is at mostTemplate:Sfnp
Knuth conjectures more strongly that these numbers obey the recursive inequality