The Fréchet distance revisited and extended

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Raichel, Benjamin A.

Contributors dc:contributor

• Har-Peled, Sariel

• Frechet Distance
• Approximation Algorithms
• Realistic Input Models

Statement dc:rights

• Copyright 2011 Benjamin A. Raichel

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24109

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24109