Graduate Thesis Or Dissertation
 

Computing the Fréchet Distance Between Surfaces

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6m311w26k

Descriptions

Attribute NameValues
Creator
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 first (1+ε)-approximation algorithm and the first 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
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

In Collection:

Items