prikaz prve stranice dokumenta Algoritmi za problem umjetničke galerije
No public access
undergraduate thesis
Algoritmi za problem umjetničke galerije
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. urn:nbn:hr:168:505531
Bestvina, Ivan
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Bestvina, I. (2015). Algoritmi za problem umjetničke galerije (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:505531

Bestvina, Ivan. "Algoritmi za problem umjetničke galerije." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. https://urn.nsk.hr/urn:nbn:hr:168:505531

Bestvina, Ivan. "Algoritmi za problem umjetničke galerije." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. https://urn.nsk.hr/urn:nbn:hr:168:505531

Bestvina, I. (2015). 'Algoritmi za problem umjetničke galerije', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 28 June 2024, https://urn.nsk.hr/urn:nbn:hr:168:505531

Bestvina I. Algoritmi za problem umjetničke galerije [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2015 [cited 2024 June 28] Available at: https://urn.nsk.hr/urn:nbn:hr:168:505531

I. Bestvina, "Algoritmi za problem umjetničke galerije", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2015. Available at: https://urn.nsk.hr/urn:nbn:hr:168:505531

Metadata
TitleAlgoritmi za problem umjetničke galerije
Title (english)Art Gallery Problem Algorithms
AuthorIvan Bestvina
MentorMario Osvin Pavčević (mentor)
Committee memberMario Osvin Pavčević (predsjednik povjerenstva)
Committee memberAndrea Aglić Aljinović (član povjerenstva)
Committee memberLana Horvat Dmitrović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2015-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:505531
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2018-02-06 07:52:17