# .

# CC system

In computational geometry, a CC system or counterclockwise system is a ternary relation pqr that satisfies the axioms:

- Cyclic symmetry: If
*pqr*then*qrp*. - Antisymmetry: If
*pqr*then not*prq*. - Nondegeneracy: Either
*pqr*or*prq*. - Interiority: If
*tqr*and*ptr*and*pqt*, then*pqr*. - Transitivity: If
*tsp*and*tsq*and*tsr*, and*tpq*and*tqr*, then*tpr*.

A ternary system may be defined from any set of points in the Euclidean plane, with no three of the points collinear, by including a triple pqr in the relation whenever the corresponding three points are in counterclockwise order around the triangle that they form. CC systems were defined by Donald Knuth, who wanted to understand problems in planar geometry. Knuth proved that CC systems were essentially equivalent to a class of oriented matroids[1] and that the information given by a CC system is sufficient to define a notion of convex hulls. The enumerative combinatorics of CC systems had been pursued by computational geometers studying "horizon theorems" before Knuth.[2]

Notes

There exists a two-to-one correspondence between CC systems and "uniform acyclic oriented matroids of rank 3", according to Knuth (1992, p. 40).

Horizon theorems had been discovered independently by Chazelle, Guibas & Lee (1985, Lemma 1) and Edelsbrunner, O'Rouke & Seidel (1986, Theorem 2.7) and then refined by Bern et al. (1991, p. 40), according to Knuth (1992, p. 96–97), who also mentions the textbook presentation in Edelsbrunner (1987, Chapter 5 "Zones in arrangements" (pp. 83–96)).

References

Bern, M. W.; Eppstein, D.; Plassman, P. E.; Yao, F. F. (1991), "Horizon theorems for lines and polygons", in Goodman, J. E.; Pollack, R.; Steiger, W., Discrete and Computational Geometry: Papers from the DIMACS Special Year, DIMACS Ser. Discrete Math. and Theoretical Computer Science (6 ed.), Amer. Math. Soc., pp. 45–66, MR 92j:52023

Chazelle, B.; Guibas, L. J.; Lee, D. T. (1985), "The power of geometric duality", BIT 25 (1): 76–90, doi:10.1007/BF01934990

Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, ISBN 978-3-540-13722-1

Edelsbrunner, H.; O'Rouke, J.; Seidel, R. (1986), "Constructing arrangements of lines and hyperplanes with applications", SIAM Journal on Computing 15 (2): 341–363, doi:10.1137/0215024.

Knuth, Donald E. (1992), Axioms and hulls, Lecture Notes in Computer Science 606, Heidelberg: Springer-Verlag, pp. ix+109, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891, retrieved 5 May 2011

Undergraduate Texts in Mathematics

Graduate Studies in Mathematics

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License