CC 시스템

CC system

계산 기하학에서 CC 시스템 또는 시계 반대 방향 시스템은 유클리드 평면에서 일반 위치의 점 세 쌍의 시계방향 순서를 모형화하기 위해 도날드 크누스가 도입한 3차 관계 pqr이다.[1]

공리

CC 시스템은 모든 구별되는 p, q, r, s, t에 대해 다음과 같은 공리를 만족시키기 위해 필요하다.[2]

  1. 주기적 대칭: pqr이면 qrp.
  2. 대칭: pqr이면 prq가 아니다.
  3. 비기생성:pqr 또는 prq.
  4. 내부성:tqr, ptr, pqt일 경우 pqr.
  5. 전이성:tsp, tsq 및 tsr, tpq 및 tqr일 경우 tpr.

구별되지 않는 점의 세 쌍은 관계의 일부로 간주되지 않는다.

평면형 점 집합으로부터의 시공

CC 시스템은 유클리드 평면의 어떤 점 세트로부터도 정의될 수 있으며, 세 개의 점이 삼각형을 형성하는 삼각형 주위의 시계 반대 순서로 이 세 점을 나열할 때마다 구별되는 점의 세 pqr을 관계에 포함시킴으로써 세 개의 점이 일렬로 정렬되지 않는다.점의 데카르트 좌표를 사용하여, 삼중 pqr은 정확히 다음과 같은 시간에[3] 관계에 포함된다.

점이 일반 위치에 있다는 조건은 구별되는 p, q, r의 경우 이 행렬 결정요소가 절대 0이 아니라는 요건과 동등하다.

그러나 모든 CC 시스템이 이런 식으로 설정된 유클리드 포인트에서 나오는 것은 아니다.[4]

등가 개념

CC 시스템은 또한 유사분열 배열 또는 비교교환 연산이 (예를 들어 버블 정렬과 같이) 인접한 요소 쌍만을 비교하는 분류 네트워크로부터 정의될 수 있으며, 모든 CC 시스템은 이러한 방식으로 정의될 수 있다.[5]이 관계는 일대일 관계가 아니라, n개의 점, n개의 선이 있는 유사 배열, n개의 값에 대한 정렬 네트워크의 비이형 CC 시스템의 수는 서로 다항식 요인 내에 있다.[6]

CC 시스템과 3등급의 균일한 반복 지향적 모태 사이에는 2대 1의 일치성이 존재한다.[7]이들 매트로이드는 1개의 표시된 세포가 있는 위상학적 동등성 등급과 1-1의 일치성을 가진다.[6]

알고리즘 응용 프로그램

CC 시스템이 제공하는 정보는 CC 시스템 내에서 볼록한 선체의 개념을 정의하기에 충분하다.볼록한 선체는 세 번째 구별점 r마다 pqr이 시스템에 속하는 특성과 구별되는 점의 순서 쌍 pq의 집합이다.사이클의 세 지점마다 동일한 순환 순서로 시스템에 속하는 속성으로 사이클을 형성한다.[8]CC 시스템에 한 번에 하나씩 포인트를 추가하고, 바이너리 검색 트리를 사용하여 지금까지 추가된 포인트의 볼록 선체를 주기적 순서로 유지함으로써 유클리드 포인트의 볼록 선체에 대해 알려진 시간 범위와 일치하는 시간 O(n log n)로 볼록 선체를 구성할 수 있다.[9]

또한 선형 시간 내에 CC 시스템에서 점의 시스템을 통해 이등분 선에 해당하는 결합선뿐만 아니라 하나의 볼록한 선체 꼭지점을 찾을 수도 있다.극한 꼭지점 구조를 통해 볼록 선체에 대한 그레이엄 스캔 알고리즘을 포인트 세트에서 CC 시스템으로 일반화할 수 있으며, 비교 정렬에 필요한 비교 횟수와 일치하는(저차 항 내) CC 시스템에 대한 여러 쿼리가 가능하다.[10]

콤비네이터 열거

n개의 점에서 비이형 CC 시스템의 수는[6][11]

1, 1, 2, 3, 2, 3, 20, 242, 6405, 316835, 28627261 … (시퀀스 A006246 in OEIS)

이러한 수치는 n에서2 기하급수적으로 증가하고,[12] 반대로 실현 가능한 CC 시스템의 수는 only(n log n)에서만 기하급수적으로 증가한다.[7]

보다 정확히 말하면, n개 지점의 비이형 CC 시스템의 숫자 C는n 기껏해야[13] 존재한다.

Knuth는 이 숫자들이 반복적인 불평등에 복종한다고 더 강하게 추측한다.

메모들

  1. ^ 크누스(1992년).
  2. ^ 크누스(1992), 페이지 4.
  3. ^ 크누스(1992), 페이지 3.
  4. ^ 크누스(1992), 페이지 25-26.
  5. ^ 크누스(1992), 페이지 29-35.
  6. ^ a b c 크누스(1992), 페이지 35.
  7. ^ a b 크누스(1992), 페이지 40.
  8. ^ 크누스(1992), 페이지 45-46.
  9. ^ 크누스(1992), 페이지 47.
  10. ^ 아이히홀저, 밀츠우 & 필즈(2013년).
  11. ^ 비겔지머 & 라지즈쇼스키(2002년).
  12. ^ 크누스(1992), 페이지 37.
  13. ^ 크누스(1992), 페이지 39.

참조

  • Aichholzer, Oswin; Miltzow, Tillmann; Pilz, Alexander (2013), "Extreme point and halving edge search in abstract order types", 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), "On halving line arrangements", Discrete Mathematics, 257 (2–3): 267–283, doi:10.1016/S0012-365X(02)00430-2, MR 1935728.
  • Knuth, Donald E. (1992), Axioms and hulls, Lecture Notes in Computer Science, vol. 606, Heidelberg: Springer-Verlag, pp. ix+109, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891, S2CID 5452191, retrieved 5 May 2011.