2022/07/16 by Siu-Wing Cheng, Cheng, Siu-Wing, Haoqiang Huang +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Automated Road and Building Extraction
paper · pdf · doi:10.48550/arxiv.2207.07809
We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = \τi : i ∈ [n] \ be polygonal curves in Rd of m vertices each. Let l be any integer from [m]. We study a generalized curve simplification problem: given error bounds δi > 0 for i ∈ [n], find a curve σ of at most l vertices such that dF(σ,τi) ≤ δi for i ∈ [n]. We present an algorithm that returns a null output or a curve σ of at most l vertices such that dF(σ,τi) ≤ δi + εδmax for i ∈ [n], where δmax = maxi ∈ [n] δi. If the output is null, there is no curve of at most l vertices within a Fréchet distance of δi from τi for i ∈ [n]. The running time is O(nO(l) mO(l2) (dl/ε)O(dl)). This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in Rd, so that dF(σ,τ) ≤ (1+ε)δ and |σ| ≤ (1+α) min\|c| : dF(c,τ) ≤ δ\ for any given δ> 0 and any fixed α, ε∈ (0,1). The running time is O(mO(1/α) (d/(αε))O(d/α)). By combining our technique with some previous results in the literature, we obtain an approximation algorithm for (k,l)-median clustering. Given T, it computes a set Σ of k curves, each of l vertices, such that ∑i ∈ [n] minσ∈ Σ dF(σ,τi) is within a factor 1+ε of the optimum with probability at least 1-μ for any given μ, ε∈ (0,1). The running time is O(n mO(kl2) μ-O(kl) (dkl/ε)O((dkl/ε)log(1/μ))).