Approximating (k,)-center clustering for curves

DOI10.1137/1.9781611975482.181MaRDI QIDQ5236374zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, Martijn Struijs

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $mathcalG$ of $n$ points in Euclidean space, the problem is to determine a set $mathcalC$ of $k$ centers (not necessarily part of $mathcalG$) such that the maximum distance between a point in $mathcalG$ and its nearest neighbor in $mathcalC$ is minimized. In this paper we study the corresponding $(k,ell)$-center problem for polygonal curves under the Fr'echet distance, that is, given a set $mathcalG$ of $n$ polygonal curves in $mathbb{R}^d$, each of complexity $m$, determine a set $mathcalC$ of $k$ polygonal curves in $mathbb{R}^d$, each of complexity $ell$, such that the maximum Fr'echet distance of a curve in $mathcalG$ to its closest curve in $mathcalC$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $ell$ is part of the input, then there is no polynomial-time approximation scheme unless $mathsfP=mathsfNP$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fr'echet distance. In the case of the discrete Fr'echet distance on two-dimensional curves, we show hardness of approximation within a factor close to $2.598$. This result also holds when $k=1$, and the $mathsfNP$-hardness extends to the case that $ell=infty$, i.e., for the problem of computing the minimum-enclosing ball under the Fr'echet distance. Finally, we observe that a careful adaptation of Gonzalez' algorithm in combination with a curve simplification yields a $3$-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.

Recommendations

• $k$-median clustering under discrete Fréchet and Hausdorff distances
• scientific article; zbMATH DE number 7662168
• Clustering time series under the Fréchet distance
• Approximability of the discrete Fréchet distance
• Approximability of the discrete Fréchet distance

Cited in

(17)

• Efficient nearest-neighbor query and clustering of planar curves
• Approximate nearest neighbor for curves: simple, efficient, and deterministic
• A proposal for robust curve clustering
• $k$-median clustering under discrete Fréchet and Hausdorff distances
• Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
• scientific article; zbMATH DE number 7662168 (Why is no real title available?)
• Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
• Fréchet Distance for Uncertain Curves
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• On computing a center persistence diagram
• Approximate nearest neighbor for curves -- simple, efficient, and deterministic
• Dynamic L-budget clustering of curves
• Fast approximations and coresets for (k,)-median under dynamic time warping
• Random projections for curves in high dimensions
• Faster Fréchet distance under transformations
• Faster, deterministic and space efficient subtrajectory clustering

This page was built for publication: Approximating \((k,\ell)\)-center clustering for curves

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