- 약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘
- ㆍ 저자명
- 류상률,Ryu. Sang-l
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2002년|29권 5호|pp.274-283 (10 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 $O(n^2)$ 시간에 구하는 알고리즘을 제시한다.
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(n^2)$ time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons.