A Dimension-Reducing Fréchet Simplification Oracle

Abstract

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n\log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge 1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2{\log }^{3}n+k{\log }^{4}n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge 1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2\mathrm{polylog}n)$. For the general dimension-reduction problem, where $P$ is a curve in ${\mathbb{R}}^d$ ($d\ge 3$), $0<{\epsilon }_0<1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1\le g\le d-1$) and an integer $k\ge 1$, we construct a data structure of size $O(n\log n+f({\epsilon }_0)n)$, where $f({\epsilon }_0)=(1+1/{\epsilon }_0{)}^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+{\epsilon }_0$ times the distance of $Q^{\ast }$ to $P$, where $Q^{\ast }$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f({\epsilon }_0)k^2{\log }^{2}n)$.

21 pages, 1 figure