文章基本信息
- 标题：Approximating the Packedness of Polygonal Curves
- 本地全文：下载
- 作者：Joachim Gudmundsson ; Yuan Sha ; Sampson Wong 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：181
- 页码：1-15
- DOI：10.4230/LIPIcs.ISAAC.2020.9
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：Computational geometry; trajectories; realistic input models
