Algoritmi za određivanje najbližeg para

master's thesis

• Author: Ivo Doko
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Vjeran Hari (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-09-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu smo proučili šest algoritama za rješavanje problema najbližeg para u \(\mathbb{R}^{2}\). Pokazali smo kako se problem može riješiti determinističkim algoritmom složenosti \(O(n\log n)\), a nedeterminističkim algoritmima složenost možemo spustiti do \(O(n)\). Ipak, testiranjem smo utvrdili da je na praktičnim veličinama ulaznih podataka od egzaktnih algoritama najefikasniji onaj koji je predstavljen u odjeljku 3.1 pod imenom Divide_and_Conquer, čija složenost je \(O(n\log^{2}n)\). Na kraju smo predstavili i jedan parametrizirani heuristički algoritam složenosti \(O(\frac{n}{\log n})\) koji pronalazi približno rješenje, čija točnost se može povećati nauštrb vremena izvođenja.

Abstract (english)

In this paper we have examined six different algorithms for solving the closest pair of points problem in \(\mathbb{R}^{2}\). We have shown that the problem can be solved with deterministic algorithms in \(O(n\log n)\) time and in \(O(n)\) time with non-deterministic algorithms. However, testing these algorithms has revealed that, for practical input sizes, the most efficient exact algorithm is the one we have labelled Divide_and_Conquer which was presented in section 3.1 and which runs in \(O(n\log^{2}n)\)time. In the final chapter we have presented a parameterised simulated annealing algorithm which finds an approximate solution in \(O(\frac{n}{\log n})\) time, accuracy of which can be increased at the expense of speed.

• Keywords: problem najbližeg para; deterministički algoritam složenosti; Divide and Conquer; parametrizirani heuristički algoritam
• Keywords (english): closest pair of points problem; deterministic algorithm; Divide and Conquer; parameterised simulated annealing algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:881156
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-08 12:17:20