제한된 형태의 질의 삼각형에 대한 range search 알고리즘 = Range search algorithms for restricted triangular queries

국문 초록 (Abstract)

Range search 문제는 대표적인 기하학적 탐색 문제로서, 탐색의 대상인 점의 집합이 주어졌을 때 반복되는 질의영역에 포함되는 점을 효율적으로 찾을 수 있도록 어떻게 자료구조를 구축하는가에 대한 문제이다. 본 논문에서는 질의 다각형이 삼각형인 경우에 대한 range search 문제를 고려한다. 질의 삼각형의 세 변 중에서 몇개의 방향이 고정되는가에 따라 네 문제를 정의한다. 네 문제중 두 문제는 동일한 계산복잡도를 가짐을 보이고 다른 한 문제에 대해 두 가지 알고리즘과 그 응용을 제시한다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 문제의 정의
• 3. F2에 대한 알고리즘
• 4. 알고리즘의 응용
• 5. 결론
• 참고문헌