2020/09/16 by Joachim Gudmundsson, Gudmundsson, Joachim, Sha Yuan +3 · 2 citations
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Visualization and Analytics #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2009.07789
openalex publication_date 2020/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 2012 Driemel et al. \citeDBLP: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+ε)-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 ℝd is c-packed. We present two approximation algorithms. The first algorithm is a 2-approximation algorithm and runs in O(dn2 log n) time. In the case d=2 we develop a faster algorithm that returns a (6+ε)-approximation and runs in O((n/ε3)4/3 polylog (n/ε))) 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.