Director of Research (if dissertation) or Advisor (if thesis)
Har-Peled, Sariel
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Frechet Distance
Approximation Algorithms
Realistic Input Models
Abstract
Given two simplicial complexes, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Frechet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of Frechet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes.
Using this new algorithm we can solve a slew of new problems, from computing a median curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the median curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the median curve in near linear time, for fixed k and epsilon.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
