Computing the Fréchet Distance Between Surfaces

Graduate Thesis Or Dissertation

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6m311w26k

Descriptions

Attribute Name	Values
Creator	Xu, Hanzhong
Abstract	The Fréchet distance is a measure of similarity between curves or surfaces. The Fréchet distance between two polygons can be computed in polynomial time, but it is much harder to compute the Fréchet distance between surfaces. We present the ﬁrst (1+ε)-approximation algorithm and the ﬁrst exact algorithm for computing the Fréchet distance between two surfaces. Next, we show that computing the Fréchet distance between a surface and a triangle is in PSPACE. Combining the approximation algorithm and the exact algorithm, we present an improved version of (1+ε)-approximation algorithm. Finally, we present a new restricted class of surface, surfaces composed of large triangles, for which the Fréchet distance between them can be computed faster.
License	All rights reserved
Resource Type	Dissertation
Date Issued	2020-01-28
Degree Level	Doctoral
Degree Name	Doctor of Philosophy (Ph.D.)
Degree Field	Computer Science
Degree Grantor	Oregon State University
Commencement Year	2020
Advisor	Nayyeri, Amir
Committee Member	Palmer, Camille Zhang, Yue Hershberger, John Borradaile, Glencora
Academic Affiliation	Electrical Engineering and Computer Science
Déclaration de droits	In Copyright
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]

Parents:

This work has no parents.

Dans Collection:

La vignette	Titre	Date de téléchargement	Visibilité	actes
	XuHanzhong2020.pdf	2020-02-28	Public	Télécharger