Aproksimacijski algoritmi za računanje povprečne razdalje med točkami : delo diplomskega seminarja

Kotar Celarc, Staš (author), Cabello, Sergio (mentor)

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.

• Language: Slovenian
• Keywords: povprečna razdalja, naključna izbira, naključna projekcija, razcep na dobro ločene pare
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2019
• PID: 20.500.12556/RUL-110399
• UDC: 519.6
• COBISS.SI-ID: 18723929
• Publication date in RUL: 14.09.2019

Secondary language

• Language: English
• Title: Approximation algorithms for computing the average of distance between points

Abstract

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.

• Keywords: average distance, random choice, random projection, well separated pair decomposition