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.

[img]
Preview
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 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.

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 View Item