# Algoritmi za određivanje najbližeg para

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

 Preview
PDF
Language: Croatian

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 \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.