Minimum number of Vertex Guards Algorithm for Art Gallery Problem

Sang-Un, Lee

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

Sang-Un, Lee ¹

¹강릉원주대학교

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

art gallery problem, polygon, orthogonal polygon, vertex coloring, triangulation, dominating set
REFERENCES (12)

[web] Wikipedia / 2010 / Art Gallery Problem / http://en.wikipedia. org/wiki/Art_gallery_problem

[web] J.Barrow / 2008 / The Maths of Pylons, Art Galleries and Prisons Under the Spotlight / http://www.gresham.ac.uk/event.asp? Pageid=45&Eventid=819

[web] S. K. Ghosh / 2010 / Art Gallery Theorems and Approximation Algorithms / http://www.tcs.tifr.res.in/~ghosh/artgallery.pdf.

[web] J. Urrutia / 1996 / Art Gallery and Illumination Problems / www.matem.unam.mx/~urrutia/onl ine_papers/Art-Galleries.ps

[journal] T. C. Shermer / 1992 / Recent Results in Art Galleries / Proceedings of the IEEE 80(9)

[web] Wikipedia / 2010 / Set Cover Problem / http://en.wikipedia. org/wiki/Set_cover_problem

[confproc] A. Deshpande / 2007 / A Pseudopolynomial Time  log -Approximatiom Algorithm for Art Gallery Problems / Proc. Workshop Algorithms and Data Structures, Lecture Notes in Computer Science / Springer-Verlag : 163~174

[journal] S. Fisk / 1978 / A Short Proof of Chvatal's Watchman Theorem / Journal of Combinatorial Theory 24(3)

[web] Wikipedia / 2010 / Dominating Set / http://en.wikipedia.org/ wiki/Dominating_set / http://en.wikipedia.org/ wiki/Dominating_set

[web] I. Peterson / 1996 / Problem at the Art Gallery / http://www. maa.org/mathland/mathland_11_4.html

[web] N. Do / 2004 / Art Gallery Theorems / www.austms.org.au/Publ/Gazette/2004/Nov04/mathellaneous.pdf

[journal] A. Laurentini / 1999 / Guarding the Walls of an Art Gallery / The Visual Computer 15 : 265~278
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools