KJC Korea Journal Central

Korean | English

pISSN : 1598-849X / eISSN : 2383-9945

2020 KCI Impact Factor : 0.4
• BACK
• TOP
Home > Explore Content > All Issues > Article View

Minimum number of Vertex Guards Algorithm for Art Gallery Problem

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2011, 16(6), pp.179-186
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

1 강릉원주대학교

• ABSTRACT

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.
• KEYWORDS

• REFERENCES (12)

• KCI Citation (1)

152 Viewed

Close X