Abstract:
The Art Gallery Problem is a computational geometric problem that asks the minimum number of guards needed to cover the interior of a polygon that represents a room. Over the years, mathematicians and computer scientists have developed many algorithms for different variations of the original problem. Unfortunately, the availability of application that visualizes the problem’s solution is still uncommon. The author sees an opportunity to implement the original problem into an application that calculates the sufficient guards of an inputted 2-dimensional polygon. The objective is to optimize and visualize the problem’s solution of solving the original problem which can be used to educate the users and help relevant professional workers in their jobs to solve such real-life problems.
For the main application features, 2 different algorithms are used. The first algorithm is the implementation of Steve Fisk’s famous idea, in which a non-intersecting polygon with no holes is decomposed into triangles (triangulation) and each vertex is assigned 1 of 3 colors (red, green, blue), such that each triangle from triangulation will have exactly 1 color from each color class (tricoloring). The triangulation is done by finding and removing ears, which is known as Ear Cutting algorithm. The tricoloring is done using Backtracking m-Coloring algorithm, by checking valid configurations of coloring and choosing different paths when invalid configuration is met. The result of the polygon triangulation and tricoloring gives ⌊ 𝑛3 ⌋ guards, where n is the number of vertices.
The second algorithm calculates how many vertices are geometrically visible to each other, then the vertex with the most visible vertices is assigned as guard. This
calculation is done dynamically until all vertices are covered. This method removes unnecessary guards and gives more optimal solution. The configuration of guard assignment between the 2 algorithms are also different. The second algorithm configuration is based on vertices’ visibility, compared to the first algorithm that is arbitrary depending on the vertex order.
