Comparative Analysis of Triangulation Methods for Optimal Solutions to the Art Gallery Problem - Marzal, Jefri; Niken Rarasati; Waladi, Akhiyar; Perdana, Yogi (LPPM Universitas Islam 45 Bekasi, 2025)
Triangulation is the process of breaking down an n-sided polygon into triangles and it is necessary in deciding the optimal count and the position of guards in the Art Gallery Problem (AGP) There is a theoretical limit that has been established which states that the number of required guards needed to keep an eye on such a polygon is ⌊n/3⌋ and this research considers this as the limit. Among various triangulation methods, Ear Clipping and Minimum Weight are two primary approaches frequently used to achieve optimal solutions. Nonetheless, its comparison with other methods, more particularly the amount of guards required for the maximum theoretical figure, is still a gap in literature. The aim of this research is to create an AGP simulation program and test it against the theoretical upper bound, determining the number of guards required. 228 simple polygons with vertices varying between 10 and 110 were utilized in this research. The polygons were classified into three groups based on the ratio of convex to concave vertices: less concave vertices, equal amount of concave and convex vertices and vice versa. Result study shows that the Ear Clipping method is significantly superior to Minimum Weight in reducing guard requirements. Practically speaking, these advancements are important for the design of engineering systems such as surveillance systems and the surveillance of public spaces. In the context of building security system design and monitoring of large areas, these conclusions are of utmost importance.