Approximating (k, ℓ)-center clustering for curves

The Euclidean k-center problem is a classical problem that has been extensively studied in many areas of 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.

keywords: Computational Geometry, Graphs Theory, Trajectories

Conference Proceedings (peer-reviewed)

Anne Driemel, Irina Kostitsyna, Joachim Gudmundsson, Kevin Buchin, Maarten Löffler, Michael Horton, Rodrigo I. Silveira
Approximating (k, ℓ)-center clustering for curves
Proc. 29th Symposium on Discrete Algorithms
2922–2938, 2019

Archived Publication (not reviewed)

Anne Driemel, Irina Kostitsyna, Joachim Gudmundsson, Kevin Buchin, Maarten Löffler, Michael Horton, Rodrigo I. Silveira
Approximating (k, ℓ)-center clustering for curves
1805.01547, 2018
http://arXiv.org/abs/1805.01547

back to list