Approximating the packedness of polygonal curves

Abstract

In 2012 Driemel et al. \cite{DBLP:journals/dcg/DriemelHW12} introduced the concept of $c$-packed curves as a realistic input model. In the case when $c$ is a constant they gave a near linear time $(1+\epsilon )$-approximation algorithm for computing the Fréchet distance between two $c$-packed polygonal curves. Since then a number of papers have used the model. In this paper we consider the problem of computing the smallest $c$ for which a given polygonal curve in ${\mathbb{R}}^d$ is $c$-packed. We present two approximation algorithms. The first algorithm is a $2$-approximation algorithm and runs in $O(d{n}^2\log n)$ time. In the case $d=2$ we develop a faster algorithm that returns a $(6+\epsilon )$-approximation and runs in $O((n/{\epsilon }^3{)}^{4/3}polylog(n/\epsilon )))$ time. We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of $c$-packedness is a useful realistic input model for many curves and trajectories.

A preliminary version to appear in ISAAC 2020