Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributorTillman Miltzow
dc.contributor.advisorMiltzow, Tillmann
dc.contributor.authorJuglan, Geo
dc.date.accessioned2022-11-18T00:00:36Z
dc.date.available2022-11-18T00:00:36Z
dc.date.issued2022
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/43207
dc.description.abstractThe 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.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectThis 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.titleSolving the Art Gallery Problem using Gradient Descent
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsart gallery problem; algorithm engineering; heuristics; constrained; optimisation; polygons; cost function;
dc.subject.courseuuComputing Science
dc.thesis.id12091


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record