This was my bachelor thesis project at Faculty of Electrical Engineering and Computing, University of Zagreb, mentored by professor Mario Osvin Pavčević. Goal of the project was to implement and compare different algorithms for the art gallery problem (link). Project was finished in June 2015.
The Art Gallery problem deals with finding minimal number of guarding positions so as to enable the guards to see every point of a given polygon. Focusing on the problem of vertex guards in simple polygons, this thesis offers a comprehensive introduction through two simple algorithms, a description and complexities calculation of a modern algorithm by S.K. Ghosh, along with an optimization that decreases space and time complexity from O(n5) to O(n4). The comparison of the optimization values to a set of test results indicates an important distinction between worst-case and real-life scenarios and some differences between the orthogonal and the simple polygons. Finally, there is a theoretical description of an alternative optimization that should not change the algorithm’s complexity but could improve its performance significantly.