Doko, Ivo (2014) Algoritmi za određivanje najbližeg para. Diploma thesis, Faculty of Science > Department of Mathematics.

PDF
Language: Croatian Download (512kB)  Preview 
Abstract
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 nondeterministic algorithms. However, testing these algorithms has revealed that, for practical input sizes, the most efficient exact algorithm is the one we have labelled \texttt{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.
Item Type:  Thesis (Diploma thesis) 

Supervisor:  Nogo, Goranka 
Date:  2014 
Number of Pages:  35 
Subjects:  NATURAL SCIENCES > Mathematics 
Divisions:  Faculty of Science > Department of Mathematics 
Depositing User:  Iva Prah 
Date Deposited:  02 Jun 2015 09:01 
Last Modified:  02 Jun 2015 12:43 
URI:  http://digre.pmf.unizg.hr/id/eprint/3917 
Actions (login required)
View Item 