- 특성 다각형에서 최소링크의 경비원 경로를 구하는 알고리즘
- ㆍ 저자명
- 류상률,Ryu. Sang-Ryul
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part A. Part A
- ㆍ 권/호정보
- 2002년|4호|pp.595-602 (8 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
다각형의 내부를 경로를 따라 이동하면서 감시하는 경비원 경로는 길이 또는 링크의 최소화 등으로 구분할 수 있다. 최소링크의 경비원 경로(watchman route with minimum route)는 경로 진행에서 발생하는 방향 전환의 횟수가 최소인 경비원 경로이다. 본 논문에서는 특성 다각형인 약 가시 다각형(weakly visible polygon)에서 최소링크의 경비원 경로를 구하는 $O(N^2)$시간 알고리즘을 제시한다.
The watchman routes which an watchman patrols the interior of polygon moving along the route are classified to minimum length or minimum links. The watchman route with minimum links has minimum changes of direction in process. In this paper, we present an algorithm with $O(N^2)$ time for finding the watchman route with minimum links in the weakly visible polygons which have specific property.