20.500.12556/RUL-110399 Aproksimacijski algoritmi za računanje povprečne razdalje med točkami delo diplomskega seminarja Approximation algorithms for computing the average of distance between points V tem diplomskem delu sem raziskal nekaj algoritmov za iskanje približka povprečne razdalje med točkami. Dva algoritma, ki sta opisana, naključno izbirata točke in na podlagi vzorca izračunata približek. Opisal sem tudi algoritem, ki vse točke projicira na naključno izbrano premico. Izkaže se, da lahko na premici vsoto vseh razdalj izračunamo bistveno hitreje kot v splošnem prostoru. Zadnji algoritem pa najprej poišče razcep na dobro ločene pare, ki ga nato uporabi za izračun povprečja. Izkaže se, da pri najhitrejšem algoritmu izberemo vzorec naključnih razdalj in izračunamo njihovo povprečje. In this dissertation I examined some algorithms for approximating the average distance between points. Two of the algorithms that I examined choose points at random and then compute the approximation based on them. Another algorithm that I examined projects all points onto a randomly chosen line. Then we exploit the fact that we can compute the sum of all distances between points on a single line much quicker than in the general case. The last algorithm that I examined computes a well separated pair decomposition and uses it to compute an approximation. We find that the fastest algorithm chooses a random sample of distances and outputs their average. povprečna razdalja naključna izbira naključna projekcija razcep na dobro ločene pare average distance random choice random projection well separated pair decomposition true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2019-09-14 07:45:43 2019-09-14 07:45:46 2024-05-30 10:22:45 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.6 99293 18723929 1045.pdf 1045.pdf 1 683339AFD0A8FFD6336969607CEBF849 8bfb2d526df3f039d593b86bcb0db978ebb8c5f2008b008572bd8974b932a70d 1b75b0c9-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=122057 Fakulteta za matematiko in fiziko 0 0 0