Approximating The (Continuous) Fréchet Distance

Date

2020-08

ORCID

Journal Title

Journal ISSN

Volume Title

Publisher

item.page.doi

Abstract

We 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.

Description

Keywords

Fréchet spaces, Approximation algorithms

item.page.sponsorship

Rights

©2020 Connor Lee Colombe. All rights reserved.

Citation