Approximating The (Continuous) Fréchet Distance

dc.contributor.advisorFox, Kyle
dc.creatorColombe, Connor L.
dc.date.accessioned2020-09-23T16:45:38Z
dc.date.available2020-09-23T16:45:38Z
dc.date.created2020-08
dc.date.issued2020-08
dc.date.submittedAugust 2020
dc.date.updated2020-09-23T16:45:38Z
dc.description.abstractWe describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let P and Q be two polygonal chains with n vertices in d-dimensional Euclidean space, and let α ∈ [√n, n]. Our algorithm deterministically finds an O(α)-approximate Fréchet correspondence in time O((n³/α²) log n). In particular, we get an O(n)-approximation in near-linear O(n log n) time, a vast improvement over the previously best know result, a linear time 2ᴼ⁽ⁿ⁾-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an O(log n) factor.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10735.1/8920
dc.language.isoen
dc.rights©2020 Connor Lee Colombe. All rights reserved.
dc.subjectFréchet spaces
dc.subjectApproximation algorithms
dc.titleApproximating The (Continuous) Fréchet Distance
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.levelMasters
thesis.degree.nameMSCS

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ETD-5608-011T-261993.63.pdf
Size:
407.59 KB
Format:
Adobe Portable Document Format
Description:
Thesis

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description: