IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

The Fréchet distance revisited and extended

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/24109

Files in this item

File Description Format
PDF Raichel_Benjamin.pdf (495KB) (no description provided) PDF
Title: The Fréchet distance revisited and extended
Author(s): Raichel, Benjamin A.
Advisor(s): Har-Peled, Sariel
Department / Program: Computer Science
Discipline: Computer Science
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: M.S.
Genre: Thesis
Subject(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.
Issue Date: 2011-05-25
URI: http://hdl.handle.net/2142/24109
Rights Information: Copyright 2011 Benjamin A. Raichel
Date Available in IDEALS: 2011-05-25
Date Deposited: 2011-05
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 69
  • Downloads this Month: 1
  • Downloads Today: 0

Browse

My Account

Information

Access Key