Events Calendar

PhD Final Exam – Hanzhong Xu

Computing the \Frechet distance between surfaces

The \Frechet distance is a measure of similarity between curves or surfaces. The \Frechet distance between two polygonals can be computed in polynomial time, but it is much harder for computing the \Frechet distance between surfaces. We present the first $(1+\varepsilon)$-approximation algorithm and the first exact algorithm for computing the \Frechet distance between two surfaces. Next, we show that computing the \Frechet 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+\varepsilon)$-approximation algorithm. Finally, we present a new restricted class of surface, surfaces composed of large triangles, for which the \Frechet distance between them can be computed faster.

Major Advisor: Amir Nayyeri
Committee: Glencora Borradaile
Committee: Yue Zhang
Committee: John Hershberger
GCR: Todd S. Palmer

Tuesday, January 28, 2020 at 10:00am to 12:00pm

Kelley Engineering Center, 1005
110 SW Park Terrace, Corvallis, OR 97331

Event Type

Lecture or Presentation

Event Topic


Electrical Engineering and Computer Science
Contact Name

Calvin Hughes

Contact Email

Google Calendar iCal Outlook

Recent Activity