System CC

W geometrii obliczeniowej system CC lub system przeciwny do ruchu wskazówek zegara to trójskładnikowa relacja $pqr$ wprowadzona przez Donalda Knutha w celu modelowania zgodnego z ruchem wskazówek zegara uporządkowania trójek punktów w ogólnej pozycji na płaszczyźnie euklidesowej .

Aksjomaty

System CC musi spełniać następujące aksjomaty dla wszystkich różnych punktów p , q , r , s i t :

Symetria cykliczna: jeśli $pqr$ to $qrp$ .
Antysymetria: jeśli $pqr$ to nie $prq$ .
Niedegeneracja: albo $pqr$ albo $prq$ .
Wewnętrzność: jeśli $tqr$ i $ptr$ i $pqt$ , to $pqr$ .
Przechodniość: jeśli $tsp$ i $tsq$ i $tsr$ oraz $tpq$ i $tqr$ , to $tpr$ .

Trójki punktów, które nie są różne, nie są uważane za część relacji.

Konstrukcja z planarnych zbiorów punktów

System CC można zdefiniować z dowolnego zestawu punktów na płaszczyźnie euklidesowej , przy czym żadne trzy punkty nie są współliniowe, poprzez włączenie do relacji potrójnego pqr $różnych$ punktów, ilekroć trójka wymienia te trzy punkty w kolejności przeciwnej do ruchu wskazówek zegara wokół trójkąta, który oni formularz. Korzystając ze współrzędnych kartezjańskich punktów, potrójny pqr jest zawarty w relacji dokładnie kiedy

{\ Displaystyle \ det \ lewo ({\ rozpocząć {tablica} {ccc} x_ {p} i y_ {p} i 1 \\ x_ {q}&y_{q}&1\\x_{r}&y_{r}&1\end{tablica}}\right)>0.}

Warunek, że punkty znajdują się w ogólnej pozycji, jest równoważny wymaganiu, aby ten wyznacznik macierzy nigdy nie wynosił zero dla różnych punktów p , q i r .

Jednak nie każdy system CC pochodzi z punktu euklidesowego ustawionego w ten sposób.

Równoważne pojęcia

Systemy CC można również zdefiniować z układów pseudolinii lub z sieci sortowania, w których operacje porównania-wymiany porównują tylko sąsiednie pary elementów (jak na przykład sortowanie bąbelkowe ) i każdy system CC można zdefiniować w ten sposób. Ta relacja nie jest jeden do jednego, ale liczby nieizomorficznych systemów CC w n punktach, układów pseudolinii z n liniami i sieci sortowania na n wartościach mieszczą się w obrębie czynników wielomianowych.

Istnieje zgodność dwa do jednego między systemami CC a jednolitymi acyklicznymi zorientowanymi matroidami rzędu 3. Te matroidy z kolei mają zgodność 1: 1 z topologicznymi klasami równoważności układów pseudolinii z jedną zaznaczoną komórką .

Aplikacje algorytmiczne

Informacje dostarczane przez system CC są wystarczające do zdefiniowania pojęcia otoczki wypukłej w systemie CC. Otoczka wypukła jest zbiorem uporządkowanych par pq różnych punktów z tą właściwością, że dla co trzeciego odrębnego punktu r , pqr należy do układu. Tworzy cykl z tą właściwością, że każde trzy punkty cyklu, w tym samym porządku cyklicznym, należą do układu. Dodając punkty pojedynczo do systemu CC i utrzymując wypukły kadłub dodanych dotychczas punktów w jego cyklicznym porządku za pomocą binarnego drzewa wyszukiwania , możliwe jest skonstruowanie wypukłego kadłuba w czasie O ( n log n ), dopasowanie znanych granic czasowych dla algorytmów kadłuba wypukłego dla punktów euklidesowych.

Możliwe jest również znalezienie pojedynczego wypukłego wierzchołka kadłuba, a także kombinatorycznego odpowiednika dwusiecznej przez układ punktów z układu CC w czasie liniowym . Konstrukcja skrajnego wierzchołka umożliwia skanowania Grahama dla wypukłych łusek ze zbiorów punktów na systemy CC, z szeregiem zapytań do systemu CC, które dopasowują (w terminach niższego rzędu) liczbę potrzebnych porównań w porównaniu sortowanie .

Wyliczanie kombinatoryczne

Liczba nieizomorficznych układów CC w n punktach wynosi

1, 1, 1, 2, 3, 20, 242, 6405, 316835, 28627261 ... (sekwencja A006246 w OEIS )

Liczby te rosną wykładniczo w n ² ; natomiast liczba możliwych do zrealizowania systemów CC rośnie wykładniczo tylko w Θ( n log n ).

Dokładniej, liczba C _n nieizomorficznych układów CC w n punktach wynosi co najwyżej

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

Knuth mocniej przypuszcza, że liczby te są zgodne z rekurencyjną nierównością

{\ Displaystyle C_ {n} \ równoważnik n2 ^ {n-2} C_ {n-1}.}

Notatki

Aichholzer, Oswin; Miltzow, Tillmann; Pilz, Alexander (2013), „Ekstremalne wyszukiwanie punktów i krawędzi o połowę w abstrakcyjnych typach zamówień”, Computational Geometry , 46 (8): 970–978, doi : 10.1016/j.comgeo.2013.05.001 , MR 3061458 , PMC 3688538 , PMID 24092953 .
Beygelzimer, Alina; Radziszowski, Stanisław (2002), „O połówkowych układach linii”, Matematyka dyskretna , 257 (2–3): 267–283, doi : 10.1016/S0012-365X(02)00430-2 , MR 1935728 .
Knuth, Donald E. (1992), Aksjomaty i kadłuby , Notatki z wykładów z informatyki, tom. 606, Heidelberg: Springer-Verlag, s. ix+109, doi : 10.1007/3-540-55611-7 , ISBN 3-540-55611-7 , MR 1226891 , S2CID 5452191 , dostęp 5 maja 2011 r .