hAhn,HeeKap 연구실

본 논문은 Baxter 순열과 그 부분집합인 분리 가능 순열(separable permutation)에 대한 간결한 자료구조를 제시합니다. Baxter 순열은 o(n) 추가 비트를 사용하면서 π(i)와 π^{-1}(j) 쿼리를 각각 O(f₁(n))과 O(f₂(n)) 시간에 지원하며, 분리 가능 순열은 두 쿼리 모두 O(1) 시간에 처리합니다. 이는 Baxter 순열에 대한 첫 번째 부선형 쿼리 시간 간결 표현이며, 모자이크 평면도와 평면 양극 방향성 그래프 등에 응용됩니다.

본 연구는 원뿔빔 컴퓨터단층촬영에서 분리한 치근을 고려한 가상 치아 배열의 근평행성과 치근 노출을 평가했습니다. 16명의 대구치 원심이동 환자를 대상으로 치관만 고려한 배열, 치근 정렬을 고려한 배열-1, 치근과 치조골을 고려한 배열-2를 비교한 결과, 배열-2에서 치근 노출이 유의하게 감소하고 근평행성이 개선되었으나 교합 품질에는 영향을 주지 않았습니다.

본 논문은 평면상의 n개 직사각형 장애물이 있는 환경에서 m개 점 사이트의 측지 L₁ 최원점 보로노이 다이어그램을 계산하는 알고리즘을 제시합니다. 이 알고리즘은 O(nm + n log n + m log m) 시간과 O(nm) 공간으로 구성되며, 장애물이 있는 환경에서 최원점 보로노이 다이어그램을 구성하는 최초의 최적 알고리즘입니다. 동일한 시간과 공간으로 구성된 자료구조는 O(log(n+m)) 시간에 최원점 이웃 질의에 응답합니다.

본 논문은 두 볼록다각형의 최대 겹침 넓이를 구하는 알고리즘을 연구합니다. 병진 이동 시 n개 꼭지점의 볼록다각형과 직사각형의 최대 겹침을 O(n) 시간에 구하는 알고리즘을 제시하며, 이를 확장하여 두 볼록다각형의 최대 겹침을 O(n+m²log³n) 시간에 구합니다. 추가로 병진이동과 강체이동 시 (1-ε) 근사 알고리즘을 제시합니다.