초록 close

2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 O(n2) 시간에 구하는 알고리즘을 제시한다.


A weakly visible polygon is an n-gon in the plane and consists of two mutually weakly visible chains. In this paper, we present an O(n2) time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons.