# Approximating (k,ℓ)-center clustering for curves

arXiv: https://arxiv.org/abs/1805.01547 · HTML: https://mlsanity.com/paper/1805.01547/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2018.

## Built on by (most cited first, 2 of 2)

- [Classifying Spatial Trajectories](https://mlsanity.com/paper/2209.01322/) (2022)
- [CSMapping: Scalable Crowdsourced Semantic Mapping and Topology Inference for Autonomous Driving](https://mlsanity.com/paper/2512.03510/) (2025)

## Abstract (arXiv)

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'echet 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'echet distance of a curve in G to its closest curve in C 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 ℓ 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 ℓ=∞, 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.