최대 폭을 갖는 k - 밀집 회랑을 구하는 동적 알고리즘 = Dynmaic Algorithm for Maintaining Widest k - dense Corridors

국문 초록 (Abstract)

이차원 공간에 n개의 점들이 주어져 있을 때, 회랑(corridor)은 그 점들의 볼록 헐과 교차하는 평행한 두개의 직선에 의해 정의되는 열려진 영역으로 정의된다. 그 영역내에 정확히 k개의 점들은 포함하고 있다면 그 회랑을 k-밀집 회랑(k-dense corridor)이라 부른다. 본 논문에서는 매 번 삽입되거나 삭제되는 동적환경에서 폭이 가장 큰 k-밀집 회랑을 유지하는 문제를 다룬다. 본 논문에서 제시하는 알고리즘은 일반적인 k(≥0)에 대한 첫번째 동적 알고리즘이며, 하나의 삽입과 삭제연산을 수행하는데 O(kn log n)시간이 걸리고 O(n²)공간이 사용된다.

목차 (Table of Contents)

• 1 서론
• 2 기하학적인 기반지식
• 3 최대 폭을 갖는 k - 밀집 회랑을 구하는 동적 알고리즘
• 4 결론
• 참고 문헌