Approximating (k,ℓ)-center clustering for curves

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

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

23 Citations (Scopus)
2 Downloads (Pure)


The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet 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 NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet 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.

Read More:
Original languageEnglish
Title of host publication30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsTimothy M. Chan
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Number of pages17
ISBN (Electronic)978-1-61197-548-2
Publication statusPublished - 2 Jan 2019
EventACM-SIAM Symposium on Discrete Algorithms (SODA2019) - San Diego, United States
Duration: 6 Jan 20199 Jan 2019


ConferenceACM-SIAM Symposium on Discrete Algorithms (SODA2019)
Abbreviated titleSODA2019
Country/TerritoryUnited States
CitySan Diego
Internet address


Dive into the research topics of 'Approximating (k,ℓ)-center clustering for curves'. Together they form a unique fingerprint.

Cite this