@article{ART001561209},
author={Sang-Un, Lee},
title={Minimum number of Vertex Guards Algorithm for Art Gallery Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2011},
volume={16},
number={6},
pages={179-186}
TY - JOUR
AU - Sang-Un, Lee
TI - Minimum number of Vertex Guards Algorithm for Art Gallery Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2011
VL - 16
IS - 6
PB - The Korean Society Of Computer And Information
SP - 179
EP - 186
SN - 1598-849X
AB - This paper suggests the minimum number of vertex guards algorithm. Given 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 vertices as follows. Firstly, you can triangulate with 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.
KW - art gallery problem;polygon;orthogonal polygon;vertex coloring;triangulation;dominating set
DO -
UR -
ER -
Sang-Un, Lee. (2011). Minimum number of Vertex Guards Algorithm for Art Gallery Problem. Journal of The Korea Society of Computer and Information, 16(6), 179-186.
Sang-Un, Lee. 2011, "Minimum number of Vertex Guards Algorithm for Art Gallery Problem", Journal of The Korea Society of Computer and Information, vol.16, no.6 pp.179-186.
Sang-Un, Lee "Minimum number of Vertex Guards Algorithm for Art Gallery Problem" Journal of The Korea Society of Computer and Information 16.6 pp.179-186 (2011) : 179.
Sang-Un, Lee. Minimum number of Vertex Guards Algorithm for Art Gallery Problem. 2011; 16(6), 179-186.
Sang-Un, Lee. "Minimum number of Vertex Guards Algorithm for Art Gallery Problem" Journal of The Korea Society of Computer and Information 16, no.6 (2011) : 179-186.
Sang-Un, Lee. Minimum number of Vertex Guards Algorithm for Art Gallery Problem. Journal of The Korea Society of Computer and Information, 16(6), 179-186.
Sang-Un, Lee. Minimum number of Vertex Guards Algorithm for Art Gallery Problem. Journal of The Korea Society of Computer and Information. 2011; 16(6) 179-186.
Sang-Un, Lee. Minimum number of Vertex Guards Algorithm for Art Gallery Problem. 2011; 16(6), 179-186.
Sang-Un, Lee. "Minimum number of Vertex Guards Algorithm for Art Gallery Problem" Journal of The Korea Society of Computer and Information 16, no.6 (2011) : 179-186.
