Approximating the packedness of polygonal curves

DOI10.1016/J.COMGEO.2022.101920MaRDI QIDQ2088893zbMATH OpenOpenAlexWikidataFDO

Authors Yuan Sha, Sampson Wong, Joachim Gudmundsson

Publication date 6 October 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.07789

zbMATH Keywords

\(c\)-packedcomputational geometryrealistic input modelstrajectories

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

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+varepsilon)$-approximation algorithm for computing the Fr'echet 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}logn)$ time. In the case $d=2$ we develop a faster algorithm that returns a $(6+varepsilon)$-approximation and runs in $O((n/varepsilo{n}^3{)}^{4/3}polylog(n/varepsilon)))$ 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.

Recommendations

• Approximating the Fréchet distance for realistic curves in near linear time
• Approximating the Fréchet distance for realistic curves in near linear time
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Jaywalking your dog: computing the Fréchet distance with shortcuts

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Approximate Map Matching with respect to the Fréchet Distance
• Approximating the Fréchet distance for realistic curves in near linear time
• Comparison of distance measures for planar curves
• Computational geometry. Algorithms and applications.
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Cutting hyperplanes for divide-and-conquer
• Fast algorithms for approximate Fréchet matching queries in geometric trees
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Fréchet Distance for Curves, Revisited
• Geometric optimization and sums of algebraic functions
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Linear size binary space partitions for uncluttered scenes
• Motion planning in environments with low obstacle density
• Partitioning arrangements of lines. II: Applications
• Probabilistic embeddings of the Fréchet distance
• Range Searching and Point Location among Fat Objects
• Realistic input models for geometric algorithms
• Reporting and counting segment intersections

Cited in

(6)

• The size of spanning disks for polygonal curves
• Approximating the Fréchet distance for realistic curves in near linear time
• Curve packing and modulus estimates
• Approximating the -low-density value
• Computing a subtrajectory cluster from c-packed trajectories
• Approximating the Fréchet distance when only one curve is c-packed

This page was built for publication: Approximating the packedness of polygonal curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2088893)