Graduate Thesis Or Dissertation


Computing the Fréchet Distance Between Surfaces Público Deposited

Contenido Descargable

Descargar PDF


Attribute Name LabelAttribute Values Label
  • 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 Label
Resource Type
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantors
Graduation Year
Contributor Advisor
Contributor Committeemember
Academic Affiliation
Declaración de derechos


Relationships Parent Rows Label

Rows Empty Text

En Collection: