Računanje Fréchetove razdalje med krivuljama

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2013
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[M. Vučkovič]
UDK:	004.4:519.6(043.2)
COBISS:	9693780
Št. ogledov:	44
Št. prenosov:	1
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Computing the Fréchet distance between curves
Sekundarni povzetek:	Comparing curves is an important and common problem in computer science. Curves are usually compared as sets of points, for example using the Hausdorff distance. Such an approach can lead to unrealistic results. Fréchet distance, which we explain in this thesis, is a natural measure of similarity between curves because it uses the curves in their entirety and respects their parametrization. There exists a discrete variant of the Fréchet distance which also respects the flow of the curves. In practice, this variant has a much better performance because of simpler primitive operations. The purpose of this thesis is to show the extension of algorithms for computing the Fréchet distance from polygonal curves to smooth curves, with some limitations. We provide concrete algorithms for solving the decision and optimization problems of Fréchet distance for smooth curves, provided some primitive operations are available. We prove that such algorithms make the same number of primitive operations as algorithms for polygonal curves: O(n^2) for the decision problem and O(n^2 log^2(n)) for the optimization problem, when the curves consist of n joined elementary pieces. We conclude that the running times of the primitive operations of these algorithms are too large to be useful in practice, and that the discrete variant of the Fréchet distance is still a better option.
Sekundarne ključne besede:	curves;Fréchet distance;parametric search;computer science;computer and information science;computer science and mathematics;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univerza v Ljubljani, Fakulteta za računalništvo in informatiko
Strani:	67 str.
ID:	24181872