Gudmundsson, Joachim ;
Sha, Yuan ;
Wong, Sampson
Approximating the Packedness of Polygonal Curves
Abstract
In 2012 Driemel et al. [Anne Driemel et al., 2012] introduced the concept of cpacked 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 cpacked 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 cpacked. We present two approximation algorithms. The first algorithm is a 2approximation 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 packednessvalue for 16 sets of realworld trajectories. The experiments indicate that the notion of cpackedness is a useful realistic input model for many curves and trajectories.
BibTeX  Entry
@InProceedings{gudmundsson_et_al:LIPIcs:2020:13353,
author = {Joachim Gudmundsson and Yuan Sha and Sampson Wong},
title = {{Approximating the Packedness of Polygonal Curves}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {9:19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13353},
URN = {urn:nbn:de:0030drops133530},
doi = {10.4230/LIPIcs.ISAAC.2020.9},
annote = {Keywords: Computational geometry, trajectories, realistic input models}
}
04.12.2020
Keywords: 

Computational geometry, trajectories, realistic input models 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 