2026-07-25T09:51:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13353 2024-03-06T10:51:46Z ddc:004 open_access

Approximating the Packedness of Polygonal Curves Gudmundsson, Joachim Sha, Yuan Wong, Sampson Computational geometry trajectories realistic input models In 2012 Driemel et al. [Anne Driemel et al., 2012] 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(dn² log n) time. In the case d = 2 we develop a faster algorithm that returns a (6+ε)-approximation and runs in O((n/ε³)^{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Gudmundsson and Yuan Sha and Sampson Wong 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.9 urn:nbn:de:0030-drops-133530 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode