본문 바로가기
  • Home

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 : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.