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,\ell)-center problem for polygonal curves under the Fr\'echet distance, that is, given a set G of n polygonal curves in R^d, each of complexity m, determine a set C of k polygonal curves in R^d, each of complexity \ell, such that the maximum Fr\'echet distance of a curve in G to its closest curve in C is minimized.  We show that  there is no polynomial-time (\frac{3{2}-\varepsilon)-approximation algorithm for any \varepsilon~>~0 }  unless \mathsf{P}=\mathsf{NP}. This bound even holds for one-dimensional curves under the continuous Fr\'echet distance , and is further improved to (3\sin(\frac{\pi{3})-\varepsilon) if the curves may lie in the plane and if the }  discrete Fr\'echet distance is used. These hardness results hold even when k=1, -hardness extends to the case that \ell=\infty, } i.e., for the  minimum-enclosing ball version of the problem. At the same time, we prove 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 give a comprehensive analysis of this approximation scheme in spaces of arbitrary dimension and for both the discrete and continuous Fr\'echet distances. Overall, our results significantly extend and improve the known approximation bounds for the (k,\ell)-center clustering problem .
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,\ell)-center problem for polygonal curves under the Fr\'echet distance, that is, given a set G of n polygonal curves in R^d, each of complexity m, determine a set C of k polygonal curves in R^d, each of complexity \ell, 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 \ell is part of the input, then there is no polynomial-time {2}-\varepsilon)-approximation algorithm for any \varepsilon~>~0 } approximation scheme unless \mathsf{P}=\mathsf{NP}. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fr\'echet distance {3})-\varepsilon) if the curves may lie in the plane and if the } . 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 \mathsf{NP-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 .
D
many areas of
A
In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher.
A
, if \ell is part of the input, then
D
(\frac{3
A
approximation scheme
R
This bound even holds for one-dimensional curves under the
Our constructions yield different bounds for one and two-dimensional curves and the discrete and
D
, and is further improved to (3\sin(\frac{\pi
A
. In the case of the
R
is used. These hardness results hold even
on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds
A
and the \mathsf{NP
A
problem of computing the
R
version of the problem. At the same time, we prove
under the Fr\'echet distance. Finally, we observe
R
give a comprehensive analysis of this approximation scheme in spaces of arbitrary dimension and for both the discrete and continuous Fr\'echet distances. Overall, our results significantly extend and improve the known approximation bounds for the (k,\ell)-center clustering problem
conclude that our approximation bounds are close to being tight