화랑 문제의 최소 정점 경비원 수 알고리즘 = Minimum number of Vertex Guards Algorithm for Art Gallery Problem

국문 초록 (Abstract)

본 논문은 화랑 문제의 최소 정점 경비원 수를 구하는 알고리즘을 제안하였다. n개의 사각형 방으로 구성된 화랑의 최소 경비원수는 정확한 해를 구하는 공식이 제안되었다. 그러나 단순하거나 장애물이 있는 다각형 또는 직각 다각형에 대해 최대 경비원수를 구하는 공식만이 제안되었으며, 최소 경비원수를 구하는 근사 알고리즘만이 제안되고 있다. n개의 정점으로 구성된 다각형 P에 대한 최대 정점 경비원 수를 구하는 방법은 Fisk가 다음과 같이 제안하였다. 첫 번째로, n-2개의 삼각형으로 구성된 삼각분할을 수행한다. 두 번째로 3색-정점색칠을 한다. 세 번째로 최소 원소를 가진 채색수를 정점 경비원의 위치로 결정한다. 본 논문에서는 지배집합으로 최소 정점 경비원 수를 구한다. 첫 번째로, 가능한 모든 가시적인 정점들 간에 간선을 그린 가시성 그래프를 얻는다. 두 번째로, 가시성그래프로부터 직접 지배집합을 얻는 방법과 가시성 행렬로부터 지배집합을 얻는 방법을 적용하였다. 다양한 화랑 문제에 적용한 결과 제안된 알고리즘은 단순하면서도 최소 정점 경비원 수를 얻을 수 있었다.

다국어 초록 (Multilingual Abstract)

This paper suggests the minimum number of vertex guards algorithm. Given n rooms, the exact number of minimum vertex guards is proposed. However, only approximation algorithms are presented about the maximum number of vertex guards for polygon and orthogonal polygon without or with holes. Fisk suggests the maximum number of vertex guards for polygon with n vertices as follows. Firstly, you can triangulate with n-2 triangles. Secondly, 3-chromatic vertex coloring of every triangulation of a polygon. Thirdly, place guards at the vertices which have the minority color. This paper presents the minimum number of vertex guards using dominating set. Firstly, you can obtain the visibility graph which is connected all edges if two vertices can be visible each other. Secondly, you can obtain dominating set from visibility graph or visibility matrix. This algorithm applies various art galley problems. As a results, the proposed algorithm is simple and can be obtain the minimum number of vertex guards.

참고문헌 (Reference)

1 J.Barrow, "The Maths of Pylons, Art Galleries and Prisons Under the Spotlight"

2 Wikipedia, "Set Cover Problem"

3 T. C. Shermer, "Recent Results in Art Galleries" 80 (80): 1992

4 I. Peterson, "Problem at the Art Gallery"

5 A. Laurentini, "Guarding the Walls of an Art Gallery" 15 : 265-278, 1999

6 Wikipedia, "Dominating Set"

7 J. Urrutia, "Art Gallery and Illumination Problems"

8 S. K. Ghosh, "Art Gallery Theorems and Approximation Algorithms"

9 N. Do, "Art Gallery Theorems"

10 Wikipedia, "Art Gallery Problem"

11 S. Fisk, "A Short Proof of Chvatal's Watchman Theorem" 24 (24): 1978

12 A. Deshpande, "A Pseudopolynomial Time  log -Approximatiom Algorithm for Art Gallery Problems" Springer-Verlag 163-174, 2007