Art Gallery Problem Untuk 1-Guarded Guards Dan 2-Guarded Guards Pada Poligon Orthogonal
Keywords:
Art gallery problem for guarded guards, Art gallery problem for 2-guarded guards, Pewarnaan graf, Poligon orthogonalAbstract
The Art Gallery Problem for k-guarded guards is the problem of determining the minimum number of guards who can each see k other guards (k-guarded guards) and can monitor all parts of a polygon with n vertices. The placement of k-guarded guards is necessary to enhance the security of a room against theft, not only from external visitors but also from the guards themselves. This research discusses the art gallery problem for k-guarded guards on orthogonal polygons for k=1 and k=2. For k=1, known as the Art Gallery Problem for 1-guarded guards, the problem has been solved through the concept of graph coloring. In this study, a new theorem is constructed using the same concept as a solution for k=2. Furthermore, the placement of 1-guarded guards is implemented in a department store in the city of Bandung.
Keywords: Art gallery problem for 2-guarded guards, Art gallery problem for guarded guards, Graph coloring, Orthogonal polygon
ABSTRAK
Art Gallery Problem for k-guarded guards adalah masalah penentuan jumlah minimal penjaga yang dapat melihat k penjaga lainnya (k-guarded guards) dan dapat mengawasi seluruh bagian poligon dengan simpul. Penempatan k-guarded guards diperlukan untuk meningkatkan pengawasan suatu ruangan dari pencurian yang bukan hanya berasal dari pengunjung luar, tetapi juga dari penjaga. Penelitian ini membahas art gallery problem for k-guarded guards pada poligon orthogonal untuk dan . Untuk yang dikenal dengan art gallery problem for 1-guarded guards, masalah telah diselesaikan melalui konsep pewarnaan graf. Pada penelitian ini dikontruksi teorema baru melalui konsep yang sama sebagai penyelesaian untuk . Selanjutnya, penempatan 1-guarded guards diimplementasikan pada suatu toserba di kota Bandung.
References
Chvátal, V. (1975). A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18(1), 39-41.
Fisk, S. (1977). A Short Proof of Chvatal's Watchman Theorm. Combinatorial Theory B 24, 374.
Michael, T. (2009). How to Guard an Art Gallery and Other Discrete Mathematical Adventures.
Michael, T. S., & Pinciu, V. (2003). Art gallery theorems for guarded guards. Computational Geometry, 26(3), 247-258.
O'Rourke, J. (1987). Art Gallery Theorems and Algorithms. New York: Oxford University Press, Inc.
Worman, C., & Keil, J. M. (2007). Polygon decomposition and the orthogonal art gallery problem. International Journal of Computational Geometry & Applications, 17(02), 105-138.
