커크패트릭-사이델 알고리즘

Kirkpatrick–Seidel algorithm

저자들이 잠재적인 "최상의 평면 볼록 껍질 알고리즘"으로 제안한 Kirkpatrick-Seidel 알고리즘은 에 있는 점들의 집합의 볼록 껍질을 계산하는 알고리즘으로, O ⁡ h) {\displaystyle }}(nlog h)} 시간 복잡도를 가지며, 여기서 은 입력 지점의 수이고 는 선체에 있는 지점의 수(일부 텍스트에서 호출된 것처럼 지배되지 않거나 최대 지점)입니다. 따라서 알고리즘은 출력에 민감합니다. 즉, 실행 시간은 입력 크기와 출력 크기 모두에 따라 달라집니다. 또 다른 출력 민감 알고리즘인 선물 포장 알고리즘은 훨씬 이전에 알려져 있었지만, Kirkpatrick-Seidel 알고리즘은 점근적 실행 시간이 상당히 작고 비출력 민감 의 O ⁡ n) {\displaystyle n\log n)} 경계에서 항상 개선됩니다. 커크패트릭-사이델 알고리즘은 발명가인 데이비드 G. 커크패트릭과 레이문드 사이델의 이름을 따서 지어졌습니다.[1]

알고리즘은 점근적으로 최적이지만 중간 크기의 문제에는 그다지 실용적이지 않습니다.[2]

알고리즘.

이 알고리즘의 기본 아이디어는 저자들이 '결혼 전 정복'이라고 부르는 프레파타와 홍의 볼록 껍질에 대한 일종의 분할 정복 알고리즘을 뒤집는 것입니다.

전통적인 분할정복 알고리즘은 예를 들어 입력 지점을 수직선으로 동일한 두 부분으로 분할하고 입력의 왼쪽 및 오른쪽 하위 집합에 대해 볼록한 선체를 재귀적으로 찾은 다음 위와 아래에서 두 선체를 연결하는 비탄젠트인 "브리지 에지"를 찾아 두 선체를 하나로 병합합니다.

Kirkpatrick-Seidel 알고리즘은 입력 지점의 x좌표의 중앙값을 찾아 입력을 이전과 같이 분할합니다. 그러나 이 알고리즘은 후속 단계의 순서를 반대로 하는데, 다음 단계는 이 중앙값 x좌표에 의해 정의된 수직선과 교차하는 볼록한 선체의 가장자리를 찾는 것이며, 이는 선형 시간이 필요한 것으로 밝혀졌습니다.[3] 분할선의 좌우에 있는 최종 선체에 기여할 수 없는 점들은 폐기되고, 나머지 점들에 대해서는 알고리즘이 재귀적으로 진행됩니다. 더 상세하게, 알고리즘은 볼록한 선체의 상부와 하부에 대해 별도의 재귀를 수행하며, 상부 선체에 대한 재귀에서는 폐기되는 비기여점은 브리지 에지의 수직 아래에 있는 점들이고, 하부 선체에 대한 재귀에서는 브리지 에지의 수직 위에 있는 점들은 폐기되는 점들입니다.

i 재귀 레벨에서 알고리즘은 최대 2 하위 문제를 해결하며, 각각의 크기는 최대 입니다 각 하위 문제가 새로운 볼록한 선체 가장자리를찾기 때문에 고려되는 하위 문제의 총 수는 h{\h}입니다. 최악의 경우는 포인트를 버릴 수 없고 하위 문제가 가능한 한 클 때 발생합니다. 즉, 레벨 ⁡_{2}h}까지의 각 재귀 레벨에 정확히 하위 문제가 있는 경우입니다. 이 최악의 경우, 로그 ⁡ h {log h)} 레벨의 재귀와 각 레벨 내에서 고려되는 O(n) {\displaystyle {\mathcal {O}}(n)} 포인트가 있으므로 총 실행 시간은 명시된 대로 O(n 로그 ⁡ h) {\displaystyle {\mathcal {O}}(n\log h)입니다.

참고 항목

참고문헌

  1. ^ Kirkpatrick, David G.; Seidel, Raimund (1986). "The ultimate planar convex hull algorithm?". SIAM Journal on Computing. 15 (1): 287–299. doi:10.1137/0215021. hdl:1813/6417.
  2. ^ McQueen, Mary M.; Toussaint, Godfried T. (January 1985). "On the ultimate convex hull algorithm in practice" (PDF). Pattern Recognition Letters. 3 (1): 29–34. Bibcode:1985PaReL...3...29M. doi:10.1016/0167-8655(85)90039-X. The results suggest that although the O(n Log h) algorithms may be the 'ultimate' ones in theory, they are of little practical value from the point of view of running time.
  3. ^ Kirkpatrick / Seidel (1986), 10쪽, 정리 3.1