단순 다각형에서의 대각 가시성 문제에 대한 효율적인 알고리즘

김수환, 신성용, 좌경룡 · 1993

대각 경비원은 다각형에 에지나 내부 대각선을 따라 움직이는 경비원이다. 한 명의 대각 경비원에 의해 경비될 수 있는 다각형을 대각 가시 다각형이라고 부르고, 대각 경비원이 위치한 대각선을 경비 대각선이라고 부른다. 우리는 다각형 P에서의 대각 가시성에 관한 다음의 세가지 문제를 고려한다. 첫째, P가 대각 가시 다각형인지를 판별하라. 둘째, P의 모든 경비 대각선을 구하라. 세째, 질의 대각선이 주어졌을때, 그것이 경비 대각선인지를 판별하라. 우리는 전처리 과정으로 모든 경비 대각선의 정보를 저장하는 자료 구조를 O(nlogn) 시간과 O(n) 공간으로 구축한다. 그리고, 이 자료 구조를 이용하면, 이들 세 문제가 각각 O(nlogn), O(nlogn+k), O(1) 시간에 해결될 수 있음을 보인다. 여기서, k는 경비 대각선의 수이다.

Cited by 0 works.

Authors