Algoritmi za problem umjetničke galerije

undergraduate thesis

• Title (english): Art Gallery Problem Algorithms
• Author: Ivan Bestvina
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem umjetničke galerije je matematički problem određivanja položaja najmanjeg broja čuvara koji svojim vidnim poljima pokrivaju cijeli zadani tlocrt opisan poligonom. U ovom radu promatrani su isključivo čuvari na vrhovima jednostavnih poligona. Cilj rada je dati uvod u moderni algoritam S. K. Ghosha kroz dva jednostavnija algoritma te ga detaljno opisati. Zatim opisati optimizaciju koja vremensku i prostornu složenost spušta s O(n^5) na O(n^4). Dani rezultati testiranja opravdavaju ovu optimizaciju, pokazuju veliku razliku između najgoreg i prosječnog praktičnog slučaja problema te ukazuju na bitne razlike između slučajnih jednostavnih i ortogonalnih poligona. Na kraju je isključivo teorijski opisana dodatna optimizacija algoritma, koja mu ne smanjuje složenost, ali poboljšava performanse.

Abstract (english)

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(n^5) to O(n^4). 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.

• Keywords: Problem umjetničke galerije; Chvátalov teorem umjetničke galerije; algoritam Avisa i Toussainta; algoritam S. K. Ghosha; set cover problem; pohlepna heuristika
• Keywords (english): Art gallery problem; Chvátals art gallery theorem; Avis – Toussaint algorithm; Ghosh’s algorithm; set cover problem; greedy heuristics
• Language: croatian
• URN:NBN: urn:nbn:hr:168:505531
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 07:52:17