CC systém - CC system

v výpočetní geometrie, a CC systém nebo systém proti směru hodinových ručiček je ternární vztah pqr představil Donald Knuth modelovat ve směru hodinových ručiček třínásobek bodů v obecná pozice v Euklidovské letadlo.[1]

Axiomy

K uspokojení následujících axiomů je zapotřebí systém CC pro všechny odlišné body p, q, r, s, a t:[2]

  1. Cyklická symetrie: Pokud pqr pak qrp.
  2. Antisymmetry: If pqr pak ne prq.
  3. Nondegeneracy: Buď pqr nebo prq.
  4. Vnitřnost: Pokud tqr a ptr a pqt, pak pqr.
  5. Transitivita: Pokud lžička a tsq a tsr, a tpq a tqr, pak tpr.

Trojice bodů, které nejsou odlišné, se nepovažují za součást vztahu.

Konstrukce z rovinných bodových sad

Systém CC lze definovat z libovolné sady bodů v systému Euklidovské letadlo, přičemž žádné tři body nejsou kolineární, zahrnutím do vztahu trojnásobek pqr zřetelných bodů, kdykoli trojice vypsá tyto tři body v pořadí proti směru hodinových ručiček kolem trojúhelníku, který tvoří. Za použití Kartézské souřadnice bodů, trojnásobek pqr je do vztahu zahrnuto přesně kdy[3]

Podmínka, že body jsou v obecné poloze, je ekvivalentní požadavku této matice určující není nikdy nula pro odlišné body p, q, a r.

Ne každý systém CC však pochází z takto nastaveného euklidovského bodu.[4]

Ekvivalentní pojmy

Systémy CC lze také definovat z pseudoline uspořádání nebo z třídění sítí ve kterém operace porovnávání a výměny porovnávají pouze sousední páry prvků (jako například třídění bublin ) a tímto způsobem lze definovat každý systém CC.[5] Tato relace není jedna ku jedné, ale počet neizomorfních CC systémů n body, ujednání o pseudoline s n linek a třídění sítí na n hodnoty, jsou v polynomiálních faktorech navzájem.[6]

Mezi systémy CC a uniformní acyklikou existuje vzájemná korespondence orientované matroidy z hodnost 3.[7] Tyto matroidy zase mají korespondenci 1-1 s třídami topologické ekvivalence pseudolinových uspořádání s jednou označenou buňkou.[6]

Algoritmické aplikace

Informace poskytované systémem CC jsou dostatečné k definování pojmu a konvexní obal v systému CC. Konvexní trup je množina uspořádaných párů pq odlišných bodů s vlastností, že pro každý třetí odlišný bod r, pqr patří do systému. Tvoří cyklus s vlastností, že každé tři body cyklu ve stejném cyklickém pořadí patří do systému.[8] Přidáním bodů jeden po druhém do systému CC a udržováním konvexního trupu dosud přidaných bodů v jeho cyklickém pořadí pomocí binární vyhledávací strom, je možné zkonstruovat konvexní trup v čase Ó(n logn), což odpovídá známým časovým limitům pro konvexní trupové algoritmy pro euklidovské body.[9]

Je také možné najít jediný konvexní vrchol trupu, stejně jako kombinatorický ekvivalent půlící čáry přes systém bodů, ze systému CC v lineární čas. Konstrukce extrémního vrcholu umožňuje Grahamovo skenování algoritmus pro konvexní trupy, který má být zobecněn z bodových sad na systémy CC, s řadou dotazů na systém CC, který odpovídá (v rámci podmínek nižšího řádu) počtu potřebných srovnání srovnávací třídění.[10]

Kombinatorický výčet

Počet neizomorfních CC systémů na n body jsou[6][11]

1, 1, 1, 2, 3, 20, 242, 6405, 316835, 28627261 ... (sekvence A006246 v OEIS )

Tato čísla exponenciálně rostou n2;[12] na rozdíl od toho počet realizovatelných systémů CC exponenciálně roste pouze v Θ (n logn).[7]

Přesněji číslo Cn neizomorfních CC systémů na n maximálně bodů[13]

Knuth silněji předpokládá, že se tato čísla řídí rekurzivní nerovností

Poznámky

  1. ^ Knuth (1992).
  2. ^ Knuth (1992), str. 4.
  3. ^ Knuth (1992), str. 3.
  4. ^ Knuth (1992), s. 25–26.
  5. ^ Knuth (1992), str. 29–35.
  6. ^ A b C Knuth (1992), str. 35.
  7. ^ A b Knuth (1992), str. 40.
  8. ^ Knuth (1992), str. 45–46.
  9. ^ Knuth (1992), str. 47.
  10. ^ Aichholzer, Miltzow & Pilz (2013).
  11. ^ Beygelzimer & Radziszowski (2002).
  12. ^ Knuth (1992), str. 37.
  13. ^ Knuth (1992), str. 39.

Reference

  • Aichholzer, Oswin; Miltzow, Tillmann; Pilz, Alexander (2013), „Hledání extrémních bodů a hran na polovinu v typech abstraktního řádu“, Výpočetní geometrie, 46 (8): 970–978, doi:10.1016 / j.comgeo.2013.05.001, PAN  3061458, PMC  3688538, PMID  24092953.
  • Beygelzimer, Alina; Radziszowski, Stanisław (2002), „O uspořádání na polovinu“, Diskrétní matematika, 257 (2–3): 267–283, doi:10.1016 / S0012-365X (02) 00430-2, PAN  1935728.
  • Knuth, Donald E. (1992), Axiomy a trupy, Přednášky v informatice, 606, Heidelberg: Springer-Verlag, str. Ix + 109, doi:10.1007/3-540-55611-7, ISBN  3-540-55611-7, PAN  1226891, vyvoláno 5. května 2011.