dc.rights.license | CC-BY-NC-ND | |
dc.contributor | Tillman Miltzow | |
dc.contributor.advisor | Miltzow, Tillmann | |
dc.contributor.author | Juglan, Geo | |
dc.date.accessioned | 2022-11-18T00:00:36Z | |
dc.date.available | 2022-11-18T00:00:36Z | |
dc.date.issued | 2022 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/43207 | |
dc.description.abstract | The Art Gallery Problem is one of the central problems in computational geometry. It was recently shown that the problem is ∃R-complete. Thus it is unlikely to be solvable by methods that are usually applied to NP-complete problems. These methods include heuristics with provable guarantees to come as close as possible to the optimal solution in polynomial time. Nonetheless, one of the most important methods to solve ∃R-complete problems is called gradient descent. Curiously, there was no attempt yet to solve the Art Gallery Problem with gradient descent. By aiming to maximise the area seen by the guards in the Art Gallery Problem, we get a continuous cost function, which allows us to compute the gradient. Using the gradient and other heuristics inspired from neural networks, we try to solve the Art Gallery Problem practically using gradient descent. Specifically, we aim to use the library CGAL. Implementations show how feasible this approach is. We visualise the results and discuss the performance of the algorithm on different input shapes and sizes. | |
dc.description.sponsorship | Utrecht University | |
dc.language.iso | EN | |
dc.subject | This thesis is an algorithm engineering paper. Namely, it implements an algorithm for solving a constrained version the Art Gallery Problem. The constrained problem consists of defining a continuous cost function for the Art Gallery Problem, and solving it for a set number of guards. The algorithm is implemented in C++. The thesis presents state-of-the-art heuristics and discusses a preliminary comparison in terms of their performance. | |
dc.title | Solving the Art Gallery Problem using Gradient Descent | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | art gallery problem; algorithm engineering; heuristics; constrained; optimisation; polygons; cost function; | |
dc.subject.courseuu | Computing Science | |
dc.thesis.id | 12091 | |