Faculty of Mathematics and Physics, University of Ljubljana, Slovenia and
Institute of Mathematics, Physics and Mechanics,
<EMAIL_ADDRESS>lj.sihttps://orcid.org/0000-0002-3183-4126Research partially supported by the
Slovenian Research Agency (P1-0297, J1-2452, N1-0218, N1-0285) Department of
Computer Science, City, University of London,
UKPanos.Giannopoulos@city.ac.ukhttps://orcid.org/0000-0002-6261-1961 Sergio
Cabello and Panos Giannopoulos [500]Theory of computation Computational
geometry

# On $k$-means for segments and polylines

Sergio Cabello  Panos Giannopoulos

###### Abstract

We study the problem of $k$-means clustering in the space of straight-line
segments in $\mathbb{R}^{2}$ under the Hausdorff distance. For this problem,
we give a $(1+\epsilon)$-approximation algorithm that, for an input of $n$
segments, for any fixed $k$, and with constant success probability, runs in
time
$O(n+\varepsilon^{-O(k)}+\varepsilon^{-O(k)}\cdot\log^{O(k)}(\varepsilon^{-1}))$.
The algorithm has two main ingredients. Firstly, we express the $k$-means
objective in our metric space as a sum of algebraic functions and use the
optimization technique of Vigneron [39] to approximate its minimum. Secondly,
we reduce the input size by computing a small size coreset using the
sensitivity-based sampling framework by Feldman and Langberg [21, 22]. Our
results can be extended to polylines of constant complexity with a running
time of $O(n+\varepsilon^{-O(k)})$.

###### keywords:

$k$-means clustering, segments, polylines, Hausdorff distance, Fréchet mean

##  1 Introduction

The $k$-_means_ clustering problem is as follows: Given a point set in a
metric space, find a set of points, called _centers_ , such that the sum of
the squared distances from each input point to its closest center is minimized
(over all possible choices of centers). It is a fundamental algorithmic
problem with a ubiquitous role in data analysis in numerous application
domains. As such, it has been studied extensively in geometric and general
metric spaces, under various constraints on the objective and the choice of
centers, and with a focus on complexity lower and upper bounds and the quality
of the (approximate) solution [1, 2, 3, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18,
21, 22, 25, 28, 31, 33].

In geometric settings, almost all previous work involves clustering points in
some low- or high-dimensional Euclidean space. A notable exception is the
relatively recent work on $k$-_center_ [5] and $k$-_median_ [6, 10, 19, 36]
clustering for polygonal curves; for $k$-center, one seeks to minimize the
maximum distance to the closest center, while for $k$-median, one seeks to
minimize just the sum of the distances (instead of the sum of the squares) to
the closest centers. We are not aware of any work on $k$-means clustering for
more complex objects than points. In this paper, we consider the $k$-means
problem in the spaces of segments and of polylines of constant complexity in
the plane with respect to the Hausdorff distance.

###  1.1 Formalization of the problem

Let $(\mathcal{S},d_{H})$ be the metric space of closed straight-line segments
in $\mathbb{R}^{2}$, where $d_{H}$ is the Hausdorff distance. Given a set $S$
of $n$ weighted segments, where each $s\in S$ has an associated positive
weight $w_{s}\in\mathbb{R}_{>0}$, and for any $k$ segments $s_{1},\dots,s_{k}$
playing the role of “centers” of the clusters, we define the objective
function

$\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})\leavevmode\nobreak\
:=\leavevmode\nobreak\ \sum_{s\in
S}w_{s}\cdot\min\\{d_{H}^{2}(s_{1},s),\dots,d_{H}^{2}(s_{k},s)\\}$

and define the $k$-means problem as the problem of finding a minimizer, i.e.,
a set of segments $S^{*}=\\{s^{*}_{1},\dots,s^{*}_{k}\\}$ that minimizes the
above cost. Note here that quite often we deal with _unweighted_ input
segments. However, for technical reasons (made clear later in our discussion)
in order to incorporate coresets in our algorithm, we have to consider the
more general case of weighted segments. Also note that we study the
_continuous_ version of the problem, where the solution segments can come from
anywhere in $(\mathcal{S},d_{H})$. This is harder than the so-called
_discrete_ version, where the solution segments have to be selected among the
input segments.

We also consider the $k$-means problem for polylines, each with a bounded
number of segments, under the Hausdorff distance, where the definition of the
problem is analogous.

We remark here on an interesting connection to the older and closely related
concept of the _Fréchet mean_ [24]. This is a generalization of the classic
notion of mean or average to any abstract metric space. For a finite point set
$P$ in a metric space $(\mathcal{M},d)$, a Fréchet mean is any minimizer of
the so-called _Fréchet variance_
$\operatorname{cost}_{P}(q)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sum_{p\in P}d^{2}(q,p)$, taken over all $q\in\mathcal{M}$. For Euclidean
spaces, the Fréchet mean is the usual arithmetic mean. (Other usual means can
be recovered as Fréchet means by considering other distances.) The Fréchet
mean is a well-studied concept in Statistics and in Riemannian spaces, where
sometimes it is known as Karcher mean, see [37] for a general, comprehensive
treatment. Computing a Fréchet-mean is precisely the $1$-means clustering
problem while the $k$-means is the generalization where the cost of each
cluster is given by the functional defining the Fréchet mean.

###  1.2 Results

Our main result is a $(1+\varepsilon)$-approximation algorithm for the
$k$-means problem in $(\mathcal{S},d_{H})$. The algorithm runs in
$O\left(\left(n+\varepsilon^{-16k+4-\eta}+\varepsilon^{-12k-3}\log^{4k+1}(\varepsilon^{-1})\right)(\log(1/\delta)\right)$
time, for any fixed $k$, any $\eta>0$, and with success probability at least
$1-\delta$ (the constant hidden in the $O$-notation depends on $\eta$ and
$k$).

There are two main ingredients in our algorithm. For the first one, described
in Section 3, we express the $k$-means objective in the space
$(\mathcal{S},d_{H})$ as a sum of algebraic functions of constant description
complexity. This algebraic approach allows us to use the optimization
technique of Vigneron [39] for approximating the minimum. This is, to the best
of our knowledge, the first application of this technique in the context of
clustering. While this technique is very expensive when applied directly to
the entire set of input segments, we can decrease the running time
dramatically by combining it with coresets. This is the second ingredient of
our algorithm, described in Section 4, namely, we use the sensitivity
framework of Feldman and Langberg [21, 22] to compute a small coreset of the
input and then we apply the former algebraic approach to the coreset.

We then extend this result to polylines of description complexity at most
$\ell=O(1)$. In this context, each input polyline and each solution polyline
has at most $\ell$ segments, but we may put in the solution polylines that are
not part of the input. The running time becomes
$O\left(\left(n+\varepsilon^{-O(k\ell)}\right)\log(1/\delta)\right)$.

We start with a side-result, given in Section 2, where we consider the Fréchet
mean (or $1$-means) problem in a concrete example with two perpendicular
segments that intersect at their centers. We show that even in this simple
setting the set of Fréchet means is surprisingly complex. The optimum is
attained in a 3-dimensional subset of the 4-dimensional parameter space needed
to model the space of candidate segments. This example also prompts to the
benefit of looking into an algebraic approach for the general setting.

###  1.3 Related work

For general metric spaces, $k$-means (as well as $k$-median) clustering is
APX-hard (when $k$ is part of the input) [15, 26]. Several polynomial-time,
constant factor approximation algorithms are known for both the continuous and
discrete versions of the problem [1, 8]. For the discrete version, there even
exist algorithms that achieve factors arbitrarily close to the lower bound
[26] and run in FPT-time with respect to $k$ and the approximation error
$\varepsilon$ [17].

The Euclidean $k$-means, where the input is a set of points in
$\mathbb{R}^{d}$, is NP-hard for $d=2$ [33] and APX-hard when $d=\omega(\log
n)$ [2]. The problem admits EPTASs with respect to $k$ and $\varepsilon$ [31]
and with respect to $d$ and $\varepsilon$ [11, 13].

As for the Fréchet mean, it has been considered for persistence diagrams [35,
38], point sets on the unit circle [7], and in the space of graphs [23, 30,
34], to name a few metric spaces far from the Euclidean setting.

###  1.4 Definitions and notation

For each point $p\in\mathbb{R}^{2}$, we use $x(p)$ and $y(p)$ for its two
coordinates. Thus, $p=(x(p),y(p))$. For any two points $p,q\in\mathbb{R}^{2}$,
we denote by $pq$ the segment with endpoints $p$ and $q$, and by $|pq|$ the
Euclidean distance between them: $|pq|^{2}=(x(p)-x(q))^{2}+(y(p)-y(q))^{2}$.
For simplicity we assume that all input segments have positive length.

Recall that the Hausdorff distance $d_{H}(A,B)$ between any two closed subsets
$A,B\subset\mathbb{R}^{2}$ is defined by

$d_{H}(A,B)=\max\Bigl{\\{}\max_{a\in A}\min_{b\in B}|ab|,\,\max_{b\in
B}\min_{a\in A}|ab|\Bigr{\\}}.$

Define $\delta(a,B)=\min_{q\in B}|ab|$ for the (directed) distance from a
point $a$ to a closed set $B$. It is well known and easy to see that for any
two segments $s_{1}=a_{1}b_{1}$ and $s_{2}=a_{2}b_{2}$ in $\mathcal{S}$

$d_{H}(s_{1},s_{2})=\max\\{\delta(a_{1},s_{2}),\delta(b_{1},s_{2}),\delta(a_{2},s_{1}),\delta(b_{2},s_{1})\\}.$
(1)

##  2 An example of Fréchet mean in $(\mathcal{S},d_{H})$

Let $s_{1}=a_{1}b_{1}$, $s_{2}=a_{2}b_{2}$ be perpendicular segments, centered
at the origin $o$, with $|s_{1}|=|s_{2}|=2$; see Figure 2. We show that the
set of Fréchet means in this case is 3-dimensional. Since a candidate Fréchet
mean is a segment, described by four parameters, this example shows that even
in relatively simple cases the space of Fréchet means may have a complex
structure and the maximum is attained at a large subset that is described
algebraically.

Let $D$ be the disk centered at $o$ with radius $1$ and let
$D_{1},\dots,D_{4}$ be the disks centered at $a_{1}/2,a_{2}/2,b_{1}/2,b_{2}/2$
with radius $\tfrac{1}{2}$. The region $D\setminus(D_{1}\cup\dots\cup D_{4})$
has four connected regions. Let $A_{i}$ be the closure of the connected region
in the $i$-th quadrant; see Figure 2.

######  Theorem 2.1.

A segment is a Fréchet mean of $\\{s_{1},s_{2}\\}$ if and only if it goes
through the origin and has its endpoints in different regions
$A_{1},\dots,A_{4}$.

Before proving the theorem, we show the following technical statement.

######  Lemma 2.2.

Consider any two segments $ab$ and $a^{\prime}b^{\prime}$ in the plane. Let
$a^{\prime\prime}b^{\prime\prime}$ be the segment obtained by translating
$a^{\prime}b^{\prime}$ such that its center coincides with the center of $ab$.
Then $d_{H}(ab,a^{\prime\prime}b^{\prime\prime})\leq
d_{H}(ab,a^{\prime}b^{\prime})$. Furthermore, if the center of $ab$ does not
lie on $a^{\prime}b^{\prime}$ and the center of $a^{\prime}b^{\prime}$ does
not lie on $ab$, then
$d_{H}(ab,a^{\prime\prime}b^{\prime\prime})<d_{H}(ab,a^{\prime}b^{\prime})$.

######  Proof 2.3.

Figure 1: Translating $a^{\prime}b^{\prime}$ so that the centers of $ab$ and
$a^{\prime}b^{\prime}$ coincide. The shaded region contains the points of the
plane at distance at most $\delta(a^{\prime},ab)$ from $ab$.

Without loss of generality we may assume that
$\delta(a^{\prime},ab)\geq\delta(b^{\prime},ab)$. See Figure 1. Note that

$\delta(a^{\prime\prime},ab)\leq\delta(a^{\prime},ab),$

and equality can occur only when the center of $a^{\prime}b^{\prime}$ lies on
$ab$. Because of symmetry we have
$\delta(a^{\prime\prime},ab)=\delta(b^{\prime\prime},ab)$. Therefore

$\max\\{\delta(a^{\prime\prime},ab),\delta(b^{\prime\prime},ab)\\}=\delta(a^{\prime\prime},ab)\leq\delta(a^{\prime},ab)=\max\\{\delta(a^{\prime},ab),\delta(b^{\prime},ab)\\},$

and equality can occur only when the center of $a^{\prime}b^{\prime}$ lies on
$ab$. Exchanging the roles of $ab$ and $a^{\prime}b^{\prime}$, we also have

$\max\\{\delta(a,a^{\prime\prime}b^{\prime\prime}),\delta(b,a^{\prime\prime}b^{\prime\prime})\\}\leq\max\\{\delta(a,a^{\prime}b^{\prime}),\delta(b,a^{\prime}b^{\prime})\\},$

and equality can occur only when the center of $ab$ lies on
$a^{\prime}b^{\prime}$. We then have

$\displaystyle d_{H}(ab,a^{\prime}b^{\prime})$
$\displaystyle=\max\\{\delta(a,a^{\prime}b^{\prime}),\delta(b,a^{\prime}b^{\prime}),\delta(a^{\prime},ab),\delta(b^{\prime},ab)\\}$
$\displaystyle\geq\max\\{\delta(a,a^{\prime\prime}b^{\prime\prime}),\delta(b,a^{\prime\prime}b^{\prime\prime}),\delta(a^{\prime\prime},ab),\delta(b^{\prime\prime},ab)\\}$
$\displaystyle=d_{H}(ab,a^{\prime\prime}b^{\prime\prime}).$

Moreover, when the center of $ab$ does not lie on $a^{\prime}b^{\prime}$ and
the center of $a^{\prime}b^{\prime}$ does not lie on $ab$, the inequality is
strict.

######  Proof 2.4 (Proof of Theorem 2.1).

Figure 2: For the set of segments $S=\\{s_{1},s_{2}\\}$, there is an infinite
family of Fréchet means.

Note that $d_{H}(s_{1},s_{2})=1$. Therefore, for any solution (Fréchet mean)
segment $s$ we have $d^{2}_{H}(s,s_{1})+d^{2}_{H}(s,s_{2})\leq
d^{2}_{H}(s_{1},s_{1})+d^{2}_{H}(s_{1},s_{2})=0+d^{2}_{H}(s_{1},s_{2})=1$.

Observe that any solution segment $s$ must pass through the origin. Indeed, if
such a solution $s$ does not pass through the origin, then the center of $s$
does not lie on $s_{1}$ or it does not lie on $s_{2}$. It follows from Lemma
2.2 that, by translating $s$ such that its center coincides with the origin,
both $d_{H}(s,s_{1})$ and $d_{H}(s,s_{2})$ do not increase, and at least one
of them strictly decreases. Therefore, $d^{2}_{H}(s,s_{1})+d^{2}_{H}(s,s_{2})$
strictly decreases by translating $s$ such that its center coincides with the
origin.

Next, consider a solution segment $s=ab$ that passes through the origin $o$
with its endpoints $a,b$ in the first and third quadrant, respectively. See
Figure 2. Let $a_{c}$ and $a^{\prime}$ be the points of intersection of the
supporting line $\ell$ of $s$ with the boundary of $D$ and the boundary of
$D_{2}$ respectively. Note that $\angle oa^{\prime}a_{2}$ is right. As $a$
moves from $o$ to $a^{\prime}$, we have
$\delta(a_{2},s)=|a_{2}a|>\delta(a,s_{2})$ and the unique minimum of
$|a_{2}a|$ is attained at $a=a^{\prime}$. When $a$ moves from $a^{\prime}$ to
$a_{c}$, $\delta(a_{2},s)=|a_{2}a^{\prime}|$ is constant. At $a=a_{c}$ we have
that $\delta(a_{2},s)=\delta(a_{c},s_{2})$, and beyond that
$\delta(a_{2},s)<\delta(a,s_{2})$. Similarly, the minimum value of
$\delta(a_{1},s)$ is $|a_{1}a^{\prime\prime}|$, where $a^{\prime\prime}$ is
the projection of $a_{1}$ onto $\ell$ (the intersection of $\ell$ with the
boundary of $D_{1}$). We also have that $\delta(a_{1},s)=\delta(a_{c},s_{1})$
when $a$ lies between $a^{\prime\prime}$ and $a_{c}$, and beyond $a_{c}$,
$\delta(a_{1},s)<\delta(a,s_{1})$.

Assume that $a^{\prime\prime}\in a^{\prime}a_{c}$, as in Figure 2; the other
case is symmetric. Using $\alpha:=\angle aoa_{1}$, for every position of $a$
in the segment $a^{\prime\prime}a_{c}$ we have

$\delta^{2}(a,s_{1})+\delta^{2}(a,s_{2})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\delta^{2}(a_{1},s)+\delta^{2}(a_{2},s)\leavevmode\nobreak\
=\leavevmode\nobreak\
|a_{1}a^{\prime\prime}|^{2}+|a_{2}a^{\prime}|^{2}\leavevmode\nobreak\
=\leavevmode\nobreak\
\sin^{2}\alpha+\sin^{2}(\pi/2-\alpha)\leavevmode\nobreak\
=\leavevmode\nobreak\ 1.$

For every position of $a$ in the segment $oa^{\prime\prime}$ we have
$\delta^{2}(a_{1},s)+\delta^{2}(a_{2},s)\leavevmode\nobreak\
>\leavevmode\nobreak\
|a_{1}a^{\prime\prime}|^{2}+|a_{2}a^{\prime}|^{2}\leavevmode\nobreak\
=\leavevmode\nobreak\ 1$, while for every position of $a$ past $a_{c}$ we have
that
$\delta^{2}(a,s_{1})+\delta^{2}(a,s_{2})>\delta^{2}(a_{1},s)+\delta^{2}(a_{2},s)=1$.

For the endpoint $b$ of $s$ in the third quadrant, the situation is symmetric.
Using that the Hausdorff distance is attained at some endpoint, we get that
each segment with an endpoint in $A_{1}$ and an endpoint in $A_{3}$ gives the
minimum possible value of $d^{2}_{H}(s,s_{1})+d^{2}_{H}(s,s_{2})\geq 1$, and
therefore is a Fréchet mean. The situation is symmetric for the other
quadrants.

##  3 An algebraic approach to $k$-means in $(\mathcal{S},d_{H})$

We use the following adaptation of the definition of a _nice_ family of
functions by Vigneron [39, Section 2.1]. Let
$\mathcal{F}=\\{f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\mid i\in I\\}$ be a
finite family of functions, where $I$ is some index set. We say that
$\mathcal{F}$ is _nice_ if there exists a constant $\lambda>d>0$ such that:

  * •

each $f_{i}\in\mathcal{F}$ is nonnegative and bounded;

  * •

for each $f_{i}\in\mathcal{F}$, there exists a semialgebraic set
$\operatorname*{supp}(f_{i})\subseteq\mathbb{R}^{d}$ and an algebraic function
$g_{i}$ of degree at most $\lambda$ with $f_{i}(x)=g_{i}(x)$ for
$x\in\operatorname*{supp}(f_{i})$ and $f_{i}(x)=0$ for
$x\notin\operatorname*{supp}(f_{i})$;

  * •

for each $f_{i}\in\mathcal{F}$, the semialgebraic set
$\operatorname*{supp}(f_{i})\subseteq\mathbb{R}^{d}$ is a boolean combination
of at most $\lambda$ subsets of $\mathbb{R}^{d}$, each of them defined by an
polynomial inequality of degree at most $\lambda$;

  * •

for each $f_{i}\in\mathcal{F}$, the restriction of $f_{i}$ to
$\operatorname*{supp}(f_{i})$ is continuous.

Note that the definition allows that the sets $\operatorname*{supp}(f_{i})$
are open, closed or mixed. It also allows that $f_{i}$ is discontinuous in
$\mathbb{R}^{d}\setminus\operatorname*{supp}(f_{i})$, which may include the
boundary of $\operatorname*{supp}(f_{i})$ in some cases.

Our use of this concept will be through the following result for computing an
approximation to the minimum of the function $\sum_{i}f_{i}$.

######  Theorem 3.1 (Adaptation of Theorem 3.4 in Vigneron [39]).

Assume that $\varepsilon\in(0,1)$. Let
$\mathcal{F}=\\{f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\mid i\in I\\}$ be a
nice family of $m$ functions. Define $g=\sum_{i\in I}f_{i}$ and assume that
$\min_{x\in\mathbb{R}^{d}}g(x)$ exists. Then we can compute a point
$x^{\prime}_{\varepsilon}\in\mathbb{R}^{d}$ such that
$g(x^{\prime}_{\varepsilon})\leq(1+\varepsilon)\min_{x\in\mathbb{R}^{d}}g(x)$
in time $O(m^{2d-2+\eta}+(m/\varepsilon)^{d+1}\log^{d+1}(m/\varepsilon))$ for
any $\eta>0$.111As noted in Vigneron [39], one needs to assume either the
Real-RAM model of computation (which is standard in computational geometry) or
a model where we can choose the precision of the intermediate computations,
and then the computational complexity of the algorithm depends on the desired
precision. The constant hidden in the $O$-notation depends on $\eta$ and on
$d$.

Let us first consider the simpler case of two segments and how their Hausdorff
distance is defined. We parameterize a segment $ab$ as the point
$(x(a),y(a),x(b),y(b))$ in $\mathbb{R}^{4}$. Note that in this
parameterization we have the artifact that the segments $ab$ and $ba$ give
different points in $\mathbb{R}^{4}$.

Let $\ell_{ab}$ be the line supporting a segment $ab$. For a point $p$, the
distance $\delta(p,ab)$ is given by one of the three terms $|pa|$, $|pb|$, or
$\delta(p,\ell_{ab})$. For a point $q\in\mathbb{R}^{2}$ and a segment $ab$,
let $\ell_{\perp}(q,ab)$ be the line perpendicular to $\ell_{ab}$ through $q$.
The lines $\ell_{\perp}(a,ab)$ and $\ell_{\perp}(b,ab)$ partition the plane
into three 2-dimensional faces (Figure 3) with closures

$\displaystyle\sigma(ab)$ $\displaystyle=\text{the closed slab between
$\ell_{\perp}(a,ab)$ and $\ell_{\perp}(b,ab)$},$ $\displaystyle\tau(a,ab)$
$\displaystyle=\text{the closed halfspace defined by $\ell_{\perp}(a,ab)$ that
does not contain $b$},$ $\displaystyle\tau(b,ab)$ $\displaystyle=\text{the
closed halfspace defined by $\ell_{\perp}(b,ab)$ that does not contain $a$}.$

We then have

$\delta(p,ab)\leavevmode\nobreak\ =\leavevmode\nobreak\
\begin{cases}|pa|&\text{if $p\in\tau(a,ab)$,}\\\ |pb|&\text{if
$p\in\tau(b,ab)$,}\\\ \delta(p,\ell_{ab})&\text{if
$p\in\sigma(ab)$}.\end{cases}$

From Equation (1), we conclude that, for any two segments $ab$ and
$a^{\prime}b^{\prime}$, the distance $d_{H}(ab,a^{\prime}b^{\prime})$ is given
by one of the functions in the family

$\mathcal{F}(ab,a^{\prime}b^{\prime})\leavevmode\nobreak\
:=\leavevmode\nobreak\ \bigl{\\{}|aa^{\prime}|,\leavevmode\nobreak\
|ab^{\prime}|,\leavevmode\nobreak\ |ba^{\prime}|,\leavevmode\nobreak\
|bb^{\prime}|,\leavevmode\nobreak\
\delta(a,\ell_{a^{\prime}b^{\prime}}),\leavevmode\nobreak\
\delta(b,\ell_{a^{\prime}b^{\prime}}),\leavevmode\nobreak\
\delta(a^{\prime},\ell_{ab}),\leavevmode\nobreak\
\delta(b^{\prime},\ell_{ab})\bigr{\\}}.$

Figure 3: The regions $\sigma(ab)$, $\tau(a,ab)$ and $\tau(b,ab)$.

We next argue that all the expressions involved are algebraic. A point $p$
lies on the line $\ell_{\perp}(a,ab)$ if and only the scalar product of the
vectors $\vec{ap}$ and $\vec{ab}$ is zero. This is equivalent to
$\bigl{(}x(p),y(p),x(a),y(a),x(b),y(b)\bigr{)}$ being a zero of the algebraic
(actually polynomial) function

$\psi(x,y,x_{a},y_{a},x_{b},y_{b}):=(x-x_{a})(x_{b}-x_{a})+(y-y_{a})(y_{b}-y_{a}).$

The sign of this expression also tells us which side of $\ell_{\perp}(a,ab)$
the point $p$ lies on. Note that this function is linear in $x$ and $y$, while
it is quadratic in $x_{a}$ and $y_{a}$. Symmetrically, the sign of
$\psi\bigl{(}x(p),y(p),x(b),y(b),x(a),y(a)\bigr{)}$ tells us which side of
$\ell_{\perp}(b,ab)$ point $p$ lies on.

In the following, we will treat the segment $a^{\prime}b^{\prime}$ as
variable, identified with $\mathbb{R}^{4}$, while the segment $ab$ will be
fixed. We will show that the space $\mathbb{R}^{4}$ can be decomposed into
cells such that, within a cell, the distance $d_{H}(ab,a^{\prime}b^{\prime})$
is defined always by the same function from
$\mathcal{F}(ab,a^{\prime}b^{\prime})$. Such a decomposition is given by the
eight algebraic hypersurfaces describing the conditions

$\displaystyle a^{\prime}\in\ell_{\perp}(a,ab),\leavevmode\nobreak\
b^{\prime}\in\ell_{\perp}(a,ab),\leavevmode\nobreak\
a^{\prime}\in\ell_{\perp}(b,ab),\leavevmode\nobreak\
b^{\prime}\in\ell_{\perp}(b,ab),$ $\displaystyle
a\in\ell_{\perp}(a^{\prime},a^{\prime}b^{\prime}),\leavevmode\nobreak\
b\in\ell_{\perp}(a^{\prime},a^{\prime}b^{\prime}),\leavevmode\nobreak\
a\in\ell_{\perp}(b^{\prime},a^{\prime}b^{\prime}),\leavevmode\nobreak\
b\in\ell_{\perp}(b^{\prime},a^{\prime}b^{\prime}),$

together with a set of hypersurfaces, “bisectors”, each defined by the set of
points where two appropriate functions from
$\mathcal{F}(ab,a^{\prime}b^{\prime})$ meet; this will become clear shortly.
Finally, we note that each function in $\mathcal{F}(ab,a^{\prime}b^{\prime})$
is algebraic of constant degree; for example, elementary algebra shows that

$\delta^{2}(a^{\prime},\ell_{ab})\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{\Bigl{(}\bigl{(}x(b)-x(a)\bigr{)}\bigl{(}y(a)-y(a^{\prime})\bigr{)}-\bigl{(}x(a)-x(a^{\prime})\bigr{)}\bigl{(}y(b)-y(a)\bigr{)}\Bigr{)}^{2}}{\bigl{(}x(a)-x(b)\bigr{)}^{2}+\bigl{(}y(a)-y(b)\bigr{)}^{2}}.$

We parameterize the space of (sequences of) $k$ segments
$a_{1}b_{1},\dots,a_{k}b_{k}$ (the $k$ candidate cluster centers) by the point

$\bigl{(}x(a_{1}),y(a_{1}),x(b_{1}),y(b_{1}),\dots,x(a_{k}),y(a_{k}),x(b_{k}),y(b_{k})\bigr{)}\in\mathbb{R}^{4k}.$

Similarly, each $z\in\mathbb{R}^{4k}$ defines a $k$-tuple of segments with
$s_{1}(z)=a_{1}(z)b_{1}(z),\dots,s_{k}(z)=a_{k}(z)b_{k}(z)$ by taking the
inverse of the parameterization.

######  Theorem 3.2.

Let $k$ be a fixed, positive integer and let $s$ be a segment in the plane. In
$O(1)$ time we can construct a nice family
$\mathcal{F}_{s}=\\{f:\mathbb{R}^{4k}\rightarrow\mathbb{R}\\}$ of $O(1)$
functions such that

$\forall z\in\mathbb{R}^{4k}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{f\in\mathcal{F}_{s}}f(z)=\min_{i\in[k]}d^{2}_{H}(s,s_{i}(z)).$

######  Proof 3.3.

Let $s=ab$ be the fixed segment. For each index $i\in[k]$, we consider the set
$\Sigma(i)$ of 8 hypersurfaces in $\mathbb{R}^{4k}$, each of them given by one
of the following conditions

$\displaystyle a_{i}\in\ell_{\perp}(a,ab),\leavevmode\nobreak\
b_{i}\in\ell_{\perp}(a,ab),\leavevmode\nobreak\
a_{i}\in\ell_{\perp}(b,ab),\leavevmode\nobreak\ b_{i}\in\ell_{\perp}(b,ab),$
$\displaystyle a\in\ell_{\perp}(a_{i},a_{i}b_{i}),\leavevmode\nobreak\
b\in\ell_{\perp}(a_{i},a_{i}b_{i}),\leavevmode\nobreak\
a\in\ell_{\perp}(b_{i},a_{i}b_{i}),\leavevmode\nobreak\
b\in\ell_{\perp}(b_{i},a_{i}b_{i}).$

Note that here $x(a)$, $y(a)$, $x(b)$ and $y(b)$ are input data while
$x(a_{i})$, $y(a_{i})$, $x(b_{i})$ and $y(b_{i})$ are variables defining
coordinates in the parameter space $\mathbb{R}^{4k}$.

Set $\Sigma:=\cup_{i\in[k]}\Sigma(i)$ and let $\mathcal{A}_{\Sigma}$ be the
arrangement in $\mathbb{R}^{4k}$ defined by $\Sigma$. From the foregoing
discussion, we have the following property: for each cell $c$ of
$\mathcal{A}_{\Sigma}$ and each index $i\in[k]$, the set of functions
$\mathcal{F}(s,a_{i}b_{i})$ stays the same and each of the distances
$\delta(a,a_{i}b_{i}),\delta(b,a_{i}b_{i}),\delta(a_{i},ab),$ and
$\delta(b_{i},ab)$, is given by the same function from
$\mathcal{F}(s,a_{i}b_{i})$. Thus, for all $z\in c$, the distance
$d_{H}(s,s_{i}(z))$ is described by the maximum among the same four functions
from $\mathcal{F}(s,a_{i}b_{i})$.

In order to make clear that only the coordinates of $a_{i}$ and $b_{i}$ are
relevant in the functions in $\mathcal{F}(s,a_{i}b_{i})$, we change the
notation to $\mathcal{G}_{i}$ and take each function $g$ of $\mathcal{G}_{i}$
to map from $\mathbb{R}^{4k}$ to $\mathbb{R}$. Formally, for each function
$f\in\mathcal{F}(s,a_{i}b_{i})$ we put into $\mathcal{G}_{i}$ the function
$g(z):=f(ab,s_{i}(z))$.

We next define a set $\Lambda$ of algebraic hypersurfaces in $\mathbb{R}^{4k}$
playing the role of “bisectors”. For each $i,j\in[k]$ with $i\leq j$, we
define $\Lambda(i,j)$ as the hypersurfaces given by equating each function of
$\mathcal{G}_{i}$ to each function of $\mathcal{G}_{j}$. Note that each
hypersurface is defined by a polynomial equality of degree at most $6$. Since
$\mathcal{G}_{i}$ has $8$ functions for each $i\in[k]$, the set $\Lambda(i,j)$
has at most $8^{2}=64$ hypersurfaces (it is $32$ for $\Lambda(i,i)$).

Set $\Lambda:=\cup_{i\in[k]}\cup_{j\in[k],i\leq j}\Lambda(i,j)$ and let
$\mathcal{A}_{\Lambda}$ be the arrangement in $\mathbb{R}^{4k}$ induced by
$\Lambda$. For each cell $c\in\mathcal{A}_{\Lambda}$ the sign of each function
$g(z)-g^{\prime}(z)$ remains constant for $g\in\mathcal{G}_{i}$,
$g^{\prime}\in\mathcal{G}_{j}$ and $z\in c$.

Finally, let $\mathcal{A}$ be the arrangement in $\mathbb{R}^{4k}$ induced by
the hypersurfaces in $\Sigma\cup\Lambda$. Note that this is a refinement of
$\mathcal{A}_{\Sigma}$ and $\mathcal{A}_{\Lambda}$, meaning that each cell of
$\mathcal{A}$ is contained in a cell of $\mathcal{A}_{\Sigma}$ and a cell of
$\mathcal{A}_{\Lambda}$.

Consider a cell $c\in\mathcal{A}$. Since $c$ is contained in a cell of
$\mathcal{A}_{\Sigma}$, for each $i\in[k]$, each function in the set
$\Delta_{i}(c)=\\{\delta(a,s_{i}(z)),\delta(b,s_{i}(z)),\delta(a_{i}(z),ab),$
and $\delta(b_{i}(z),ab)\\}$ is given by the same function of
$\mathcal{G}_{i}$ for all $z\in c$. Moreover, since $c$ is contained in a cell
of $\mathcal{A}_{\Lambda}$, for every two distinct functions
$\delta,\delta^{\prime}\in\Delta_{i}(c)$ the sign of $\delta-\delta^{\prime}$
is constant for all $z\in c$. From these two facts we conclude that, for each
$i\in[k]$, there is some function $g_{c,i}(z)\in\mathcal{G}_{i}$ such that
$d_{H}(s,s_{i}(z))=g_{c,i}(z)$ for all $z\in c$. This function can be easily
determined in $O(1)$ time per cell by evaluating each function in
$\Delta_{i}(c)$ at some arbitrary point in $c$.

Similarly, since $c$ is contained in a cell of $\mathcal{A}_{\Lambda}$, we
have that for each distinct $i,j\in[k]$ the sign of

$d_{H}(s,s_{i}(z))-d_{H}(s,s_{j}(z))\leavevmode\nobreak\ =\leavevmode\nobreak\
g_{c,i}(z)-g_{c,j}(z)$

is constant for all $z\in c$. This implies that, for each cell
$c\in\mathcal{A}$, there exists some index $\iota(c)\in[k]$ with the following
property:

$\displaystyle\forall j\in[k],\leavevmode\nobreak\ z\in c:\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ d_{H}(s,s_{\iota(c)}(z))\leq
d_{H}(s,s_{j}(z)).$

In other words, the segment $s_{\iota(c)}(z)$ is a closest one to $s$ among
$s_{1}(z),\dots,s_{k}(z)$ and moreover the distance $d_{H}(s,s_{\iota(c)}(z))$
is given by a single function $g_{c,\iota(c)}$ from $\mathcal{G}_{\iota(c)}$.
Thus, for each $z\in c$ it holds
$\min_{i\in[k]}d_{H}(s,s_{i}(z))=g_{c,\iota(c)}(z)$. As before, the function
$g_{c,\iota(c)}(z)$ can be determined in $O(k)$ time per cell by evaluating
each $d_{H}(s,s_{i}(z))$ at some arbitrary point in $c$.

For any set $A$, let $1_{A}$ be the function with $1_{A}(x)=1$ if $x\in A$ and
$1_{A}(x)=0$ if $x\notin A$. For each cell $c\in\mathcal{A}$, define the
function $h_{c}:\mathbb{R}^{4k}\rightarrow\mathbb{R}$ by
$h_{c}(z)=1_{c}(z)\cdot g^{2}_{c,\iota(c)}(z)$. Finally, set
$\mathcal{F}_{s}:=\\{h_{c}\mid c\in\mathcal{A}\\}$. We can then express the
function

$z\in\mathbb{R}^{4k}\mapsto\min_{i\in[k]}d^{2}_{H}(s,s_{i}(z))$

as

$\min_{i\in[k]}d^{2}_{H}(s,s_{i}(z))\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{c\in\mathcal{A}}1_{c}(z)\,g^{2}_{c,\iota(c)}(z)\leavevmode\nobreak\
=\leavevmode\nobreak\ \sum_{c\in\mathcal{A}}h_{c}(z)\leavevmode\nobreak\
=\leavevmode\nobreak\ \sum_{h\in\mathcal{F}_{s}}h(z).$

Since $\Sigma\cup\Lambda$ has $O(k^{2})=O(1)$ hypersurfaces, the arrangement
$\mathcal{A}$ has $O(O(k^{2})^{4k})=O(1)$ cells, each of them described by
$O(k^{2})=O(1)$ algebraic inequalities of constant description complexity and
the family of functions $\mathcal{F}_{s}$ has the desired properties, where
the constant $\lambda$ used to define the niceness is $O(k^{8k})$.
Constructing $\mathcal{A}$ (i.e., with algebraic descriptions for each cell)
takes $O(O(k^{2})^{4k+1}6^{O((4k)^{4})})=O(1)$ [4, Chapter 16]. The family
$\mathcal{F}_{s}$ can be constructed in this time as well.

We can now apply Theorem 3.1 combining all the functions $\mathcal{F}_{s}$ for
$s\in S$ and compute a set of $k$ segments whose cost approximates that of an
optimal set of segments.

######  Theorem 3.4.

Let $k$ a fixed, positive integer and let $\varepsilon\in(0,1)$. Let $S$ be a
family of $n$ segments in the plane with positive weights. We can compute $k$
segments $s_{1,\varepsilon},\dots,s_{k,\varepsilon}$ in $\mathbb{R}^{2}$ such
that

$\operatorname{cost}_{S}(\\{s_{1,\varepsilon},\dots,s_{k,\varepsilon}\\})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
(1+\varepsilon)\min\Bigl{\\{}\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})\mid
s_{1},\dots,s_{k}\text{ segments}\Bigr{\\}}.$

in time $O(n^{8k-2+\eta}+(n/\varepsilon)^{4k+1}\log^{4k+1}(n/\varepsilon))$,
for any $\eta>0$. The constant hidden in the $O$-notation depends on $\eta$
and on $k$.

######  Proof 3.5.

For each segment $s\in S$ we compute the family $\mathcal{F}_{s}$ of Theorem
3.2. This takes $O(n)\cdot O(1)=O(n)$ time in total. To account for the weight
$w_{s}>0$ of the segment $s$, we replace in $\mathcal{F}_{s}$ each function
$f\in\mathcal{F}_{s}$ with $w_{s}\cdot f$. Define $\mathcal{F}:=\cup_{s\in
S}\mathcal{F}_{s}$ and the function $g:=\sum_{f\in\mathcal{F}}f$. Note that
$\mathcal{F}$ is a family of $O(1)\cdot O(n)=O(n)$ nice functions and

$\forall z\in\mathbb{R}^{4k}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ g(z)\leavevmode\nobreak\ =\leavevmode\nobreak\ \sum_{s\in
S}\sum_{f\in\mathcal{F}_{s}}f(z)\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{s\in S}w_{s}\cdot\min_{i\in[k]}d_{H}(s,s_{i}(z))^{2}\leavevmode\nobreak\
=\leavevmode\nobreak\ \operatorname{cost}_{S}(\\{s_{1}(z),\dots,s_{k}(z)\\}).$

We can then use Theorem 3.1 to find in time $O(|\mathcal{F}|^{2\cdot
4k-2+\eta}+(|\mathcal{F}|/\varepsilon)^{4k+1}\log^{4k+1}(|\mathcal{F}|/\varepsilon))$,
for any $\eta>0$, a point $z^{\prime}_{\varepsilon}\in\mathbb{R}^{4k}$ such
that

$g(z^{\prime}_{\varepsilon})\leavevmode\nobreak\ \leq\leavevmode\nobreak\
(1+\varepsilon)\min_{z\in\mathbb{R}^{4k}}\operatorname{cost}_{S}(\\{s_{1}(z),\dots,s_{k}(z)\\}).$

The point $z^{\prime}_{\varepsilon}\in\mathbb{R}^{4k}$ defines the segments
$s_{1,\varepsilon}:=s_{1}(z^{\prime}_{\varepsilon}),\dots,s_{k,\varepsilon}:=s_{k}(z^{\prime}_{\varepsilon})$.
Since $s_{1}(z),\dots,s_{k}(z)$ goes over all $k$ tuples of segments when $z$
iterates over all $\mathbb{R}^{4k}$, we have

$\min_{z\in\mathbb{R}^{4k}}\operatorname{cost}_{S}(\\{s_{1}(z),\dots,s_{k}(z)\\})\leavevmode\nobreak\
=\leavevmode\nobreak\
\min_{s_{1},\dots,s_{k}}\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\}).$

We conclude that

$\operatorname{cost}_{S}(\\{s_{1,\varepsilon},\dots,s_{k,\varepsilon}\\}\leavevmode\nobreak\
=\leavevmode\nobreak\ g(z^{\prime}_{\varepsilon})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
(1+\varepsilon)\min_{s_{1},\dots,s_{k}}\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\}).$

##  4 A coreset for $k$-means in $(\mathcal{S},d_{H})$

We use the sensitivity framework of Feldman and Langberg [21, 22]. Let $F$ be
a finite set of functions, each of them mapping from $\mathbb{R}^{d}$ to
$\mathbb{R}_{\geq 0}$. The _sensitivity_ of $f\in F$ with respect to $F$ is

$\sigma(f,F)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sup_{z\in\mathbb{R}^{d}}\frac{f(z)}{\displaystyle\sum_{g\in F}g(z)}.$

We also consider the following range space

$\operatorname{range_{\geq}}(F)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\left(F,\bigl{\\{}\\{f\in F\mid f(z)\geq r\\}\mid
z\in\mathbb{R}^{d},\leavevmode\nobreak\ r\in[0,\infty)\bigr{\\}}\right).$

We will use the following theorem from [22], which we state here adapted to
our needs.

######  Theorem 4.1 (Adaptation of Theorem 31 in Feldman et al. [22]).

Let $F$ be a set of $n$ functions from $\mathbb{R}^{d}$ to $[0,\infty)$ with
the following properties:

  * •

For each choice of weights $w_{f}>0$ for $f\in F$, the range space
$\operatorname{range_{\geq}}(\\{w_{f}\cdot f\mid f\in F\\})$ has bounded VC-
dimension.

  * •

For each $f\in F$ we are given a value $\tilde{\sigma}(f)$ such that

$\tilde{\sigma}(f)\geq\frac{1}{|F|}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{ and }\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \tilde{\sigma}(f)\geq\sigma(f,F).$

Set $\tilde{\Sigma}(F):=\sum_{f\in F}\tilde{\sigma}(f)$. Let
$\delta,\varepsilon$ be real values in $(0,1/2)$. In time $O(|F|)$ we can
compute a subset $C\subseteq F$ of

$O\left(\frac{\tilde{\Sigma}(F)}{\varepsilon^{2}}\left(\log\tilde{\Sigma}(F)+\log\frac{1}{\delta}\right)\right)$

weighted functions and weights $u_{f}>0$ for each $f\in C$ such that, with
probability at least $1-\delta$:

$\forall z\in\mathbb{R}^{d}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \left|\sum_{f\in F}f(z)-\sum_{f\in C}u_{f}\cdot
f(z)\right|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \varepsilon\sum_{f\in
F}f(z).$

For each input segment $s\in S$, we define the function
$f_{s}:\mathbb{R}^{4k}\rightarrow\mathbb{R}_{\geq 0}$ with

$f_{s}(z)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\min\\{d^{2}_{H}(s,s_{1}(z)),\dots,d^{2}_{H}(s,s_{k}(z))\\}\leavevmode\nobreak\
=\leavevmode\nobreak\
\bigl{(}\min\\{d_{H}(s,s_{1}(z)),\dots,d_{H}(s,s_{k}(z))\\}\bigr{)}^{2}.$

Here, the segments $s_{1}(z),\dots,s_{k}(z)$ are the same that were used in
the parameterization before Theorem 3.2. Set $F=\\{f_{s}\mid s\in S\\}$. In
order to use the above theorem, we need appropriate sensitivity upper bounds
$\tilde{\sigma}(f_{s})$ for each $f_{s}\in F$ and a bound on the total
sensitivity $\tilde{\Sigma}(F)$. Let $\operatorname{opt}_{k}(S)$ be the cost
of an optimal set of segments for $k$-means, i.e.,
$\operatorname{opt}_{k}(S)=\min_{s_{1},\dots,s_{k}}\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})$.

######  Lemma 4.2.

Let $s^{\prime}_{1}\dots,s^{\prime}_{k^{\prime}}$ be a bicriteria
$(\alpha,\beta)$-approximation for $k$-means, that is, $k^{\prime}\leq\beta k$
and
$\operatorname{cost}_{S}(\\{s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime}}\\})\leq\alpha\cdot\operatorname{opt}_{k}(S)$,
where $\alpha,\beta\geq 1$. For each $i\in[k^{\prime}]$, let $S^{\prime}_{i}$
be the segments of $S$ closer to $s^{\prime}_{i}$ than to any other segment
$s^{\prime}_{j}$, $j\in[k^{\prime}]\setminus\\{i\\}$; ties are solved
arbitrarily so that $S^{\prime}_{1},\dots,S^{\prime}_{k^{\prime}}$ is a
partition of $S$. For each segment $s\in S$, let $\iota(s)\in[k^{\prime}]$ be
such that $s\in S^{\prime}_{\iota(s)}$. Define for each $s\in S$ the value

$\tilde{\sigma}(f_{s})\leavevmode\nobreak\ :=\leavevmode\nobreak\
\frac{32\alpha}{|S^{\prime}_{\iota(s)}|}+\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{\iota(s)})}{\displaystyle\sum_{s^{\prime}\in
S^{\prime}_{\iota(s)}}d^{2}_{H}(s^{\prime},s^{\prime}_{\iota(s)})}\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{32\alpha}{|S^{\prime}_{\iota(s)}|}+\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{\iota(s)})}{\operatorname{cost}_{S^{\prime}_{\iota(s)}}(s^{\prime}_{\iota(s)})}.$

Then $\tilde{\sigma}(f_{s})\geq\sigma(f_{s},F)$ and
$\tilde{\sigma}(f_{s})\geq\frac{1}{|F|}$.

######  Proof 4.3.

Consider a fixed $s\in S$ and set $i=\iota(s)$; thus $s\in S^{\prime}_{i}$.
Define $R_{i}$ to be the average cost of the elements of $S^{\prime}_{i}$ for
the center $s^{\prime}_{i}$:

$R_{i}\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{\operatorname{cost}_{S^{\prime}_{i}}(s^{\prime}_{i})}{|S^{\prime}_{i}|}\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{\displaystyle\sum_{s^{\prime}\in
S^{\prime}_{i}}d^{2}_{H}(s^{\prime},s^{\prime}_{i})}{|S^{\prime}_{i}|}.$

With this notation we have

$\tilde{\sigma}(f_{s})\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{32\alpha}{|S^{\prime}_{i}|}+\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{i})}{\operatorname{cost}_{S^{\prime}_{i}}(s^{\prime}_{i})}\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{32\alpha}{|S^{\prime}_{i}|}+\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{i})}{|S^{\prime}_{i}|\cdot R_{i}}.$

Since $|S^{\prime}_{i}|\leq|S|=|F|$ and $\alpha\geq 1$, we have
$\tilde{\sigma}(f_{s})\geq\frac{1}{|S^{\prime}_{i}|}\geq\frac{1}{|F|}$.

For the other inequality, recall that

$\sigma(f_{s},F)\leavevmode\nobreak\ =\leavevmode\nobreak\
\sup_{z\in\mathbb{R}^{4k}}\frac{f_{s}(z)}{\displaystyle\sum_{f_{s^{\prime}}\in
F}f_{s^{\prime}}(z)}\leavevmode\nobreak\ =\leavevmode\nobreak\
\sup_{z\in\mathbb{R}^{4k}}\frac{\min\\{d^{2}_{H}(s,s_{1}(z)),\dots,d^{2}_{H}(s,s_{k}(z))\\}}{\displaystyle\sum_{s^{\prime}\in
S}\min\\{d^{2}_{H}(s^{\prime},s_{1}(z)),\dots,d^{2}_{H}(s^{\prime},s_{k}(z))\\}}.$

Consider any $z\in\mathbb{R}^{4k}$. We distinguish three cases.

First, if $z$ is such that for some $j\in[k]$ we have
$d^{2}_{H}(s,s_{j}(z))\leq 16\cdot d^{2}_{H}(s,s^{\prime}_{i})$, then we use
that
$\operatorname{cost}_{S}(\\{s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime}}\\})\leq\alpha\cdot\operatorname{opt}_{k}(S)$
to obtain

$\frac{f_{s}(z)}{\displaystyle\sum_{s^{\prime}\in
S}f_{s^{\prime}}(z)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{d^{2}_{H}(s,s_{j}(z))}{\operatorname{opt}_{k}(S)}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{i})}{\operatorname{cost}_{S}(\\{s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime}}\\})}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{i})}{\operatorname{cost}_{S^{\prime}_{i}}(s^{\prime}_{i})}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \tilde{\sigma}(f_{s}).$

Second, if $z$ is such that for some $j\in[k]$ we have
$d^{2}_{H}(s,s_{j}(z))\leq 16\cdot R_{i}$, then we use again that
$\operatorname{cost}_{S}(\\{s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime}}\\})\leq\alpha\cdot\operatorname{opt}_{k}(S)$
to obtain

$\displaystyle\frac{f_{s}(z)}{\displaystyle\sum_{s^{\prime}\in
S}f_{s^{\prime}}(z)}\leavevmode\nobreak\ $
$\displaystyle\leq\leavevmode\nobreak\
\frac{d^{2}_{H}(s,s_{j}(z))}{\operatorname{opt}_{k}(S)}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{16\alpha\cdot
R_{i}}{\operatorname{cost}_{S}(\\{s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime}}\\})}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{16\alpha\cdot
R_{i}}{\operatorname{cost}_{S^{\prime}_{i}}(s^{\prime}_{i})}\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{16\alpha\cdot R_{i}}{|S^{\prime}_{i}|\cdot
R_{i}}\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{16\alpha}{|S^{\prime}_{i}|}$ $\displaystyle\leq\leavevmode\nobreak\
\tilde{\sigma}(f_{s}).$

It remains to handle the case when, for the $z\in\mathbb{R}^{4k}$ under
consideration, we have $d^{2}_{H}(s,s_{j}(z))>16\cdot
d^{2}_{H}(s,s^{\prime}_{i})$ and $d^{2}_{H}(s,s_{j}(z))>16\cdot R_{i}$ for all
$j\in[k]$. Let $s^{\prime\prime}_{j}$ be the segment defined by $z$ that is
closest to $s$, which means that $f_{s}(z)=d^{2}_{H}(s,s^{\prime\prime}_{j})$.
We then have $d_{H}(s,s^{\prime\prime}_{j})>4\cdot d_{H}(s,s^{\prime}_{i})$
and $d_{H}(s,s^{\prime\prime}_{j})>4\cdot\sqrt{R_{i}}$. Because of the
triangular inequality for $d_{H}(\cdot,\cdot)$ and because
$s^{\prime\prime}_{j}$ is closest to $s$, for each segment $s^{\prime}\in S$
and each $\ell\in[k]$ we have

$d_{H}(s,s^{\prime\prime}_{j})\leavevmode\nobreak\ \leq\leavevmode\nobreak\
d_{H}(s,s_{\ell}(z))\leavevmode\nobreak\ \leq\leavevmode\nobreak\
d_{H}(s,s^{\prime}_{i})+d_{H}(s^{\prime}_{i},s^{\prime})+d_{H}(s^{\prime},s_{\ell}(z)).$

This means that,

$\forall s^{\prime}\in S:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\min\\{d_{H}(s^{\prime},s_{1}(z)),\dots,d_{H}(s^{\prime},s_{k}(z))\\}\leavevmode\nobreak\
\geq\leavevmode\nobreak\
d_{H}(s,s^{\prime\prime}_{j})-d_{H}(s,s^{\prime}_{i})-d_{H}(s^{\prime}_{i},s^{\prime}).$

Using that $d_{H}(s,s^{\prime}_{i})<d_{H}(s,s^{\prime\prime}_{j})/4$ we get:

$\forall s^{\prime}\in S:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\min\\{d_{H}(s^{\prime},s_{1}(z)),\dots,d_{H}(s^{\prime},s_{k}(z))\\}\leavevmode\nobreak\
\geq\leavevmode\nobreak\
\tfrac{3}{4}d_{H}(s,s^{\prime\prime}_{j})-d_{H}(s^{\prime}_{i},s^{\prime}).$

At least half of the segments $s^{\prime}\in S^{\prime}_{i}$ must have
$d^{2}_{H}(s^{\prime},s^{\prime}_{i})\leq 2R_{i}$; otherwise the average cost
of the elements of $S^{\prime}_{i}$ would be larger than $R_{i}$. Let
$S^{\prime\prime}_{i}$ be those segments $s^{\prime}$ of $S^{\prime}_{i}$ with
$d^{2}_{H}(s^{\prime},s^{\prime}_{i})\leq 2R_{i}$. We then have

$\displaystyle\forall s^{\prime}\in S^{\prime\prime}_{i}:\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\min\\{d_{H}(s^{\prime},s_{1}(z)),\dots,d_{H}(s^{\prime},s_{k}(z))\\}\leavevmode\nobreak\
$ $\displaystyle\geq\leavevmode\nobreak\
\tfrac{3}{4}d_{H}(s,s^{\prime\prime}_{j})-d_{H}(s^{\prime}_{i},s^{\prime})$
$\displaystyle\geq\leavevmode\nobreak\
\tfrac{3}{4}d_{H}(s,s^{\prime\prime}_{j})-\sqrt{2R_{i}}$
$\displaystyle\geq\leavevmode\nobreak\
\tfrac{3}{4}d_{H}(s,s^{\prime\prime}_{j})-\tfrac{1}{2\sqrt{2}}d_{H}(s,s^{\prime\prime}_{j})$
$\displaystyle\geq\leavevmode\nobreak\
\tfrac{1}{4}d_{H}(s,s^{\prime\prime}_{j}).$

and therefore

$\displaystyle\forall s^{\prime}\in S^{\prime\prime}_{i}:\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
f_{s^{\prime}}(z)=\bigl{(}\min\\{d_{H}(s^{\prime},s_{1}(z)),\dots,d_{H}(s^{\prime},s_{k}(z))\\}\bigr{)}^{2}\leavevmode\nobreak\
$ $\displaystyle\geq\leavevmode\nobreak\
\tfrac{1}{16}d^{2}_{H}(s,s^{\prime\prime}_{j}).$

It follows that

$\frac{f_{s}(z)}{\displaystyle\sum_{s^{\prime}\in
S}f_{s^{\prime}}(z)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{d^{2}_{H}(s,s^{\prime\prime}_{j})}{\displaystyle\sum_{s^{\prime}\in
S^{\prime\prime}_{i}}f_{s^{\prime}}(z)}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{d^{2}_{H}(s,s^{\prime\prime}_{j})}{|S^{\prime\prime}_{i}|\cdot\tfrac{1}{16}d^{2}_{H}(s,s^{\prime\prime}_{j})}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{2\cdot
16}{|S^{\prime}_{i}|}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\tilde{\sigma}(f_{s}).$

We have shown that

$\forall z\in\mathbb{R}^{4k}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \frac{f_{s}(z)}{\displaystyle\sum_{s^{\prime}\in
S}f_{s^{\prime}}(z)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\tilde{\sigma}(f_{s}).$

It then follows that

$\sigma(f_{s},F)\leavevmode\nobreak\ =\leavevmode\nobreak\
\sup_{z\in\mathbb{R}^{4k}}\frac{f_{s}(z)}{\displaystyle\sum_{f_{s^{\prime}}\in
F}f_{s^{\prime}}(z)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\tilde{\sigma}(f_{s}).$

Finally, note that for the sensitivities $\tilde{\sigma}(f_{s})$ defined in
Lemma 4.2, we have the total sensitivity

$\displaystyle\tilde{\Sigma}(F)\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle=\leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{s\in
S}\tilde{\sigma}(f_{s})\leavevmode\nobreak\ \leavevmode\nobreak\
=\leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{s\in
S}\left(\frac{32\alpha}{|S^{\prime}_{\iota(s)}|}+\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{\iota(s)})}{\operatorname{cost}_{S^{\prime}_{\iota(s)}}(s^{\prime}_{\iota(s)})}\right)$
$\displaystyle=\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{i\in[k^{\prime}]}\left(\sum_{s\in
S^{\prime}_{i}}\frac{32\alpha}{|S^{\prime}_{i}|}+\sum_{s\in
S^{\prime}_{i}}\frac{16\alpha\cdot
d^{2}_{H}(s,s^{\prime}_{i})}{\operatorname{cost}_{S^{\prime}_{i}}(s^{\prime}_{i})}\right)\leavevmode\nobreak\
\leavevmode\nobreak\ =\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{i\in[k^{\prime}]}\left(32\alpha+16\alpha\right)$
$\displaystyle=\leavevmode\nobreak\ \leavevmode\nobreak\ O(\beta\alpha k).$

Next, we bound the VC-dimension of the range space associated with the input
segments.

######  Lemma 4.4.

Assume that we have a weight $w_{s}>0$ for each $s\in S$ and consider the set
of functions $F_{w}=\\{w_{s}\cdot f_{s}\mid s\in S\\}$. The range space
$\operatorname{range_{\geq}}(F_{w})$ has VC-dimension $O(1)$.

######  Proof 4.5.

First note that the range space $\operatorname{range_{\geq}}(F_{w})$ is
equivalent to the range space $(S,R)$, where the ranges are

$\displaystyle R\leavevmode\nobreak\ $ $\displaystyle=\leavevmode\nobreak\
\bigl{\\{}\\{s\in S\mid(w_{s}\cdot f_{s})(z)\geq r\\}\mid
z\in\mathbb{R}^{4k},\leavevmode\nobreak\ r\in[0,\infty)\bigr{\\}}$
$\displaystyle=\leavevmode\nobreak\ \bigl{\\{}\\{s\in S\mid
w_{s}\cdot\min\\{d^{2}_{H}(s,s_{1}(z))\dots,d^{2}_{H}(s,s_{k}(z))\\}\geq
r\\}\mid z\in\mathbb{R}^{4k},\leavevmode\nobreak\ r\in[0,\infty)\bigr{\\}}$
$\displaystyle=\leavevmode\nobreak\ \bigl{\\{}\\{s\in S\mid\forall
i\in[k]:\leavevmode\nobreak\ \sqrt{w_{s}}\cdot
d_{H}(s,s_{i}(z))\geq\sqrt{r}\\}\mid z\in\mathbb{R}^{4k},\leavevmode\nobreak\
r\in[0,\infty)\bigr{\\}}.$

Setting $w^{\prime}_{s}=\sqrt{w_{s}}$ for each $s\in S$ and
$r^{\prime}=\sqrt{r}$, we get that the ranges are

$R\leavevmode\nobreak\ =\leavevmode\nobreak\ \bigl{\\{}\\{s\in S\mid\forall
i\in[k]:\leavevmode\nobreak\ w^{\prime}_{s}\cdot d_{H}(s,s_{i}(z))\geq
r^{\prime}\\}\mid z\in\mathbb{R}^{4k},\leavevmode\nobreak\
r^{\prime}\in[0,\infty)\bigr{\\}}.$

For each segment $s\in S$, consider the hypersurface $\lambda_{s}$ in
$\mathbb{R}^{4k+1}$ given by the graph of the function
$z\in\mathbb{R}^{4k}\mapsto w^{\prime}_{s}\cdot d_{H}(s,s_{i}(z))$. This is
$\lambda_{s}\leavevmode\nobreak\ \equiv\leavevmode\nobreak\
\left\\{\bigl{(}z,w^{\prime}_{s}\cdot
d_{H}(s,s_{i}(z))\bigr{)}\in\mathbb{R}^{4k}\times\mathbb{R}\mid
z\in\mathbb{R}^{4k}\right\\}$. As it has been discussed and used in Section 3
when defining the set $\mathcal{F}(ab,a^{\prime}b^{\prime})$, the hypersurface
$\lambda_{s}$ is contained in the union of $8$ _algebraic_ hypersurfaces of
bounded degree, each of them being the graph of a function. Let $\Lambda_{s}$
be the set of those $8$ algebraic hypersurfaces for the segment $s\in S$.

Set $\Lambda:=\cup_{s\in S}\Lambda_{s}$ and let $\mathcal{A}$ be the
arrangement in $\mathbb{R}^{4k+1}$ induced by $\Lambda$. Each point
$(z,r^{\prime})\in\mathbb{R}^{4k}\times\mathbb{R}$ gives a range to $R$, and
two points in the same cell of $\mathcal{A}$ give exactly the same range to
$R$ because, for each $s\in S$, the surface $\lambda_{s}$ is above, below or
on all the points of the cell. It may happen that points in different cells of
$\mathcal{A}$ give the same range, as one still has to check the condition
$\forall i\in[k]:\leavevmode\nobreak\ w^{\prime}_{s}\cdot
d_{H}(s,s_{i}(z))\geq r^{\prime}$. In any case, the number of cells in
$\mathcal{A}$ is an upper bound to the number of ranges in $R$, which is
exactly the number of ranges in $\operatorname{range_{\geq}}(F_{w})$.

Classical results in Real Algebraic Geometry imply that $\mathcal{A}$ has
$|\Lambda|^{O(k)}$ cells; see for example [4, Chapter 7] or [32, Section 6.2].
This implies that the so-called shattering dimension of
$\operatorname{range_{\geq}}(F_{w})$ is $O(k)=O(1)$. (See for example Har-
Peled [27, Chapter 5] for the concept and the next property.) Since a range
space has bounded shattering dimension if and only if it has bounded VC-
dimension this implies that the VC-dimension of
$\operatorname{range_{\geq}}(F_{w})$ is $O(1)$. The approach we have used is
essentially an application of the methodology discussed by Matoušek [32,
Section 10.3].

Note that in this proof we have not tried to optimize the bound on the VC-
dimension because we assume $k$ is constant. Perhaps a better bound follows
from adapting the result of Driemel at al. [20] to the case of weights.

We can now apply Theorem 4.1 on $F$ to obtain the coreset.

######  Theorem 4.6.

Assume that $k$ is a fixed positive integer. Let $\delta,\varepsilon$ be real
values in $(0,1/2)$. For any set $S$ of $n$ unweighted segments in the plane,
we can compute in time $O(n\log(1/\delta))$ a subset $T\subseteq S$ of

$O\left(\varepsilon^{-2}\log\frac{1}{\delta}\right)$

segments and weights $u_{s}>0$ for each $s\in T$ such that, with probability
at least $1-\delta$:

$\forall\text{ segments }s_{1},\dots,s_{k}:\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\left|\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})-\operatorname{cost}_{T}(\\{s_{1},\dots,s_{k}\\})\right|\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\varepsilon\cdot\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\}).$

######  Proof 4.7.

We first compute a bicriteria $(\alpha=O(1),\beta=O(1))$-approximation for
$k$-means on $S$ by using the algorithm of Chen [9, Theorem A.4], which in
turn is a modification of the algorithm by Indyk [29]. For a probability of
error $\delta^{\prime}=\delta/2$, the algorithm takes
$O(n\log(1/\delta^{\prime}))=O(n\log(1/\delta))$ time and succeeds with
probability at least $1-\delta^{\prime}$ in finding a set
$s_{1},\dots,s_{k^{\prime}}$ of $k^{\prime}=O(k)$ segments such that
$\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k^{\prime}}\\})\leq
O(1)\cdot\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})$. Note that the
algorithm of Chen is for the discrete version of $k$-means, where the centers
under consideration must be a subset of $S$. However, it is well-known that
the triangle inequality implies that this is a factor $4$ off for the
continuous $k$-means version. This factor $4$ is then subsumed by the $O(1)$
approximation factor.

Let $F=\\{f_{s}\mid s\in S\\}$. We use the bicriteria approximation for the
sensitivity upper bounds $\tilde{\sigma}(f_{s})$, for each $f_{s}\in F$, as
defined in Lemma 4.2. As discussed after Lemma 4.2, the total sensitivity
$\tilde{\Sigma}(F)$ is $O(1)$ and, by Lemma 4.4, the VC-dimension of
$\operatorname{range_{\geq}}(F)$ is $O(1)$. The result then follows using
Theorem 4.1 with probability of error $\delta^{\prime}=\delta/2$. The size of
the set $C\subseteq F$ selected by Theorem 4.1 is
$O(\tilde{\Sigma}(F)\varepsilon^{-2}(\log\tilde{\Sigma}(F)+\log(1/\delta^{\prime}))=O(\varepsilon^{-2}\log(1/\delta))$,
and each function $f\in C$ has a given weight $u_{f}>0$. We set $T=\\{s\in
S\mid f_{s}\in C\\}$ and, for each segment $s\in T$, we define the weight
$w_{s}:=u_{f_{s}}$.

With probability at least $1-\delta^{\prime}$ we have

$\forall z\in\mathbb{R}^{4k}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \left|\sum_{f\in F}f(z)-\sum_{f\in C}u_{f}\cdot
f(z)\right|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \varepsilon\sum_{f\in
F}f(z),$

which can be rewritten as

$\forall z\in\mathbb{R}^{4k}:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \left|\sum_{s\in S}f_{s}(z)-\sum_{s\in T}w_{s}\cdot
f_{s}(z)\right|\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\varepsilon\sum_{s\in S}f_{s}(z).$

Since $f_{s}(z)=\min\\{d^{2}_{H}(s,s_{1}(z)),\dots,d^{2}_{H}(s,s_{k}(z))\\}$
and $s_{1}(z),\dots,s_{k}(z)$ goes over all $k$ tuples of candidate segments
when $z$ iterates over all $\mathbb{R}^{4k}$, the last statement is equivalent
to

$\forall\text{ segments }s_{1},\dots,s_{k}:\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\left|\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})-\operatorname{cost}_{T}(\\{s_{1},\dots,s_{k}\\})\right|\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\varepsilon\cdot\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\}).$

The algorithm may fail only if the bicriteria approximation of Chen fails or
if the application of Theorem 4.1 fails, and each of them separately fails
with probability at most $\delta/2$.

##  5 Putting it all together

Let $S$ be a set of $n$ segments in the plane without weights. We first set a
fixed probability of error $\delta=1/2$, which means that the terms
$\log(1/\delta)$ become $O(1)$. We keep using $\varepsilon\in(0,1/2)$ as a
parameter.

We first compute a weighted coreset $T\subseteq S$ with
$|T|=O(\varepsilon^{-2}))$ elements in $O(n)$ time as described in Theorem
4.6; for each segment $s\in T$ we have a weight $w_{s}>0$. If
$S^{*}=\\{s^{*}_{1},\ldots,s^{*}_{k}\\}$ is an optimal set of segments for
$S$, then from Theorem 4.6 we have that
$\operatorname{cost}_{T}(S^{*})\leq(1+\varepsilon)\cdot\operatorname{cost}_{S}(S^{*})$
with probability at least $1/2$.

We apply the $(1+\varepsilon)$-approximation algorithm of Theorem 3.4 on $T$,
taking into account the weights of the segments. As $|T|=O(\varepsilon^{-2})$
the algorithm runs in time

$O\left((\varepsilon^{-2})^{8k-2+\eta}+(\varepsilon^{-3})^{4k+1}\log^{4k+1}(\varepsilon^{-3})\right)\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\varepsilon^{-16k+4-\eta}+\varepsilon^{-12k-3}\log^{4k+1}(\varepsilon^{-1})\right)$

for any $\eta>0$. When $k=1$, the second summand dominates. When $k\geq 2$ and
$\varepsilon$ is below some constant $\varepsilon_{0}$, the first summand
dominates.

Let $T^{*}=\\{t^{*}_{1},\ldots,t^{*}_{k}\\}$ be an optimal set of segments for
$k$-means of the weighted set $T$. The algorithm of Theorem 3.4 has then
provided a set
$S_{\varepsilon}=\\{s_{1,\varepsilon},\dots,s_{k,\varepsilon}\\}$ of $k$
segments for which
$\operatorname{cost}_{T}(S_{\varepsilon})\leq(1+\varepsilon)\cdot\operatorname{cost}_{T}(T^{*})$.
Note that for the set $S_{\varepsilon}$ we also get from Theorem 4.6 that
$(1-\varepsilon)\cdot\operatorname{cost}_{S}(S_{\varepsilon})\leq\operatorname{cost}_{T}(S_{\varepsilon})$.
Since $\operatorname{cost}_{T}(T^{*})\leq\operatorname{cost}_{T}(S^{*})$, we
conclude that

$\displaystyle(1-\varepsilon)\cdot\operatorname{cost}_{S}(S_{\varepsilon})\leavevmode\nobreak\
$ $\displaystyle\leq\leavevmode\nobreak\
\operatorname{cost}_{T}(S_{\varepsilon})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
(1+\varepsilon)\cdot\operatorname{cost}_{T}(T^{*})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ (1+\varepsilon)\cdot\operatorname{cost}_{T}(S^{*})$
$\displaystyle\leq\leavevmode\nobreak\
(1+\varepsilon)^{2}\cdot\operatorname{cost}_{S}(S^{*})$

or

$\operatorname{cost}_{S}(S_{\varepsilon})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)}\cdot\operatorname{cost}_{S}(S^{*})\leavevmode\nobreak\
=\leavevmode\nobreak\ (1+O(\varepsilon))\cdot\operatorname{cost}_{S}(S^{*}).$

Setting $\varepsilon=\Theta(\varepsilon^{\prime})$ appropriately, we get a
$(1+\varepsilon^{\prime})$-approximation for any desired
$\varepsilon^{\prime}$.

By independently repeating the algorithm $O(\log(1/\delta))$ times and taking
the best among the solutions, we can reduce the probability of error to any
given value $\delta$. Because $k=O(1)$, evaluating each candidate solution
with respect to the whole set of segments takes $O(n)$ time. We summarize in
the following.

######  Theorem 5.1.

Let $k$ a fixed, positive integer and let $\delta,\varepsilon\in(0,1/2)$. Let
$S$ be a family of $n$ unweighted segments in the plane. We can compute $k$
segments $s_{1,\varepsilon},\dots,s_{k,\varepsilon}$ in $\mathbb{R}^{2}$ such
that, with probability at least $1-\delta$,

$\operatorname{cost}_{S}(\\{s_{1,\varepsilon},\dots,s_{k,\varepsilon}\\})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
(1+\varepsilon)\min_{s_{1},\dots,s_{k}}\operatorname{cost}_{S}(\\{s_{1},\dots,s_{k}\\})$

in time
$O\left(\left(n+\varepsilon^{-16k+4-\eta}+\varepsilon^{-12k-3}\log^{4k+1}(\varepsilon^{-1})\right)(\log(1/\delta)\right)$,
for any $\eta>0$.

For $k=1$, the running time is
$O\left(\left(n+\varepsilon^{-15}\log^{5}(\varepsilon^{-1})\right)(\log(1/\delta)\right)$,
while for $k\geq 2$ the running time is
$O\left(\left(n+\varepsilon^{-16k+4-\eta}\right)(\log(1/\delta)\right)$ for
any $\eta>0$.

##  6 Extension to polylines

In this section we briefly discuss the extension of our result to the case of
polylines of bounded complexity. To reduce the number of parameters, we assume
that each polyline has at most $\ell$ segments and we search the $k$-means
among polylines that have at most $\ell$ segments. (We can also handle the
case where the input and the target centers have different complexities.) To
simplify the discussion, we assume that each input polyline has exactly $\ell$
segments. We further assume that $\ell=O(1)$.

We regard each polyline $\pi$ as the union of segments and note that the
distance between the polyline $\pi$ with segments $s_{1},\dots,s_{\ell}$ and
the polyline $\pi^{\prime}$ with segments
$s^{\prime}_{1},\dots,s^{\prime}_{\ell}$ is

$d_{H}(\pi,\pi^{\prime})\leavevmode\nobreak\ =\leavevmode\nobreak\
\max\Bigl{\\{}\max_{i\in[\ell]}\min_{j\in[\ell]}d_{H}(s_{i},s^{\prime}_{j}),\leavevmode\nobreak\
\max_{j\in[\ell]}\min_{i\in[\ell]}d_{H}(s^{\prime}_{j},s_{i})\Bigr{\\}}.$

Therefore the distance between any two polylines is described as a max-min
combination of $O(\ell^{2})=O(1)$ values.

A polyline with $\ell$ segments is parameterized by $2(\ell+1)$ real values.
Therefore, a sequence of $k$ polylines with $\ell$ segments each is
parameterized by a point in $\mathbb{R}^{\kappa}$ for $\kappa=2k(\ell+1)$.
(Before, for segments, we had $\kappa=4k$.) Each $z\in\mathbb{R}^{\kappa}$
defines $k$ polylines $\pi_{1}(z),\dots,\pi_{k}(z)$, each consisting of $\ell$
segments.

Let $\Pi$ be a set of polylines in the plane, each with $\ell$ segments. For
each $\pi\in\Pi$, we define the function
$f_{\pi}:\mathbb{R}^{\kappa}\rightarrow\mathbb{R}$ by

$f_{\pi}(z)\leavevmode\nobreak\ :=\leavevmode\nobreak\
\min\\{d^{2}_{H}(\pi,\pi_{1}(z)),\dots,d^{2}_{H}(\pi,\pi_{k}(z))\\}\leavevmode\nobreak\
=\leavevmode\nobreak\
\bigl{(}\min\\{d_{H}(\pi,\pi_{1}(z)),\dots,d_{H}(\pi,\pi_{k}(z))\\}\bigr{)}^{2}$

and then define the set of functions $F=\\{f_{\pi}\mid\pi\in\Pi\\}$.

We first note that the VC-dimension of the range space
$\operatorname{range_{\geq}}(F_{w})$ is $O(1)$, where $F_{w}$ is obtained from
$F$ by scaling each $f_{\pi}\in F$ with a different scalar $w_{\pi}>0$. The
proof of Lemma 4.4 readily applies to this case as it only relies on the
description complexity of $d_{H}(\pi,\pi_{i}(z))$ being constant, and each
patch of the description being an algebraic function.

Next we note that we can use the bicriteria
$(\alpha=O(1),\beta=O(1))$-approximation for $k$-means of Chen, as we did in
the proof of Theorem 4.6. Indeed, this algorithm only requires that we can
compute the distance between any two input objects, which we can do in
constant time. The rest of the proof of Theorem 4.6 goes unchanged because
Lemma 4.2 and Theorem 4.1 do not make any assumption related to segments
beyond the VC-dimension. We thus obtain with probability at least $1/2$ a
coreset $\tilde{\Pi}$ of $O(\varepsilon^{-2})$ input polylines, each of them
with a positive weight $w_{\pi}$.

It remains to adapt Theorem 3.4 to the setting of polylines. As we have done
in Theorem 3.2, for each polyline $\pi$ we can compute a family
$\mathcal{F}_{\pi}$ of nice functions such that

$f_{\pi}(z)\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{f\in\mathcal{F}_{\pi}}f(z)\leavevmode\nobreak\ =\leavevmode\nobreak\
\min_{i\in[k]}d^{2}_{H}(\pi,\pi_{i}(z))\leavevmode\nobreak\
\leavevmode\nobreak\ \text{ for all $z\in\mathbb{R}^{\kappa}$.}$

Indeed, as we did in the proof of Theorem 3.2, we can break the parameter
space $\mathbb{R}^{\kappa}$ using $O(k^{2}\ell^{2})=O(1)$ algebraic
hypersurfaces into $O(1)$ cells such that, within each cell, the max-max-min
expression defining $d_{H}(\pi,\pi_{i}(z))$ is always the same algebraic
expression. We can then apply Theorem 3.1 to the family of nice functions
$\cup_{\pi\in\tilde{\Pi}}\mathcal{F}_{\pi}$, where each function in
$\mathcal{F}_{\pi}$ has been scales with the corresponding weight $w_{\pi}$.
Thus, we have an application of Theorem 3.1 in $\mathbb{R}^{\kappa}$ for
$O(\varepsilon^{-2})$ functions. The running time is, for any $\eta>0$,

$O((\varepsilon^{-2})^{2\kappa-2+\eta}+(\varepsilon^{-3})^{\kappa+1}\log^{\kappa+1}(\varepsilon^{-3}))\leavevmode\nobreak\
=\leavevmode\nobreak\
O(\varepsilon^{-4\kappa+4+\eta}+\varepsilon^{-3\kappa-3}\log^{\kappa+1}(\varepsilon^{-}1))\leavevmode\nobreak\
=\leavevmode\nobreak\ O(\varepsilon^{-O(k\ell)}).$

Like before, we can make $O(\log(1/\delta))$ independent repetitions to
decrease the probability of failure to $\delta$. We summarize below.

######  Theorem 6.1.

Let $k$ and $\ell$ be fixed, positive integers and let
$\delta,\varepsilon\in(0,1/2)$ be parameters. Let $\Pi$ be a family of $n$
unweighted polylines in the plane, each with at most $\ell$ segments. We can
compute $k$ polylines $\pi_{1,\varepsilon},\dots,\pi_{k,\varepsilon}$ in
$\mathbb{R}^{2}$, each with at most $\ell$ segments, such that, with
probability at least $1-\delta$,

$\operatorname{cost}_{\Pi}(\\{\pi_{1,\varepsilon},\dots,\pi_{k,\varepsilon}\\})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
(1+\varepsilon)\min_{\pi_{1},\dots,\pi_{k}}\operatorname{cost}_{\Pi}(\\{\pi_{1},\dots,\pi_{k}\\})$

in time $O\left(\left(n+\varepsilon^{-O(k\ell)}\right)(\log(1/\delta)\right)$.

## References

  * [1] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and Euclidean k-median by primal-dual algorithms.  SIAM J. Comput., 49(4), 2020.
  * [2] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop.  The hardness of approximation of Euclidean k-means.  In 31st International Symposium on Computational Geometry, SoCG 2015, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [3] Sayan Bandyapadhyay and Kasturi R. Varadarajan.  On variants of k-means clustering.  In 32nd International Symposium on Computational Geometry, SoCG 2016, volume 51 of LIPIcs, pages 14:1–14:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [4] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  Algorithms in Real Algebraic Geometry.  Springer Berlin, Heidelberg, 2006.
  * [5] Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, and Martijn Struijs.  Approximating $(k,\ell)$-center clustering for curves.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2922–2938. SIAM, 2019.
  * [6] Maike Buchin, Anne Driemel, and Dennis Rohde.  Approximating $(k,\ell)$-median clustering for polygonal curves.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2697–2717, 2021.
  * [7] Frédéric Cazals, Bernard Delmas, and Timothee O’Donnell.  Fréchet mean and p-mean on the unit circle: Decidability, algorithm, and applications to clustering on the flat torus.  In 19th International Symposium on Experimental Algorithms, SEA 2021, volume 190 of LIPIcs, pages 15:1–15:16, 2021.
  * [8] Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar.  Approximation algorithms for continuous clustering and facility location problems.  In 30th Annual European Symposium on Algorithms, ESA 2022, volume 244 of LIPIcs, pages 33:1–33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [9] Ke Chen.  On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications.  SIAM J. Comput., 39(3):923–947, 2009.
  * [10] Siu-Wing Cheng and Haoqiang Huang.  Curve simplification and clustering under Fréchet distance.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 1414–1432. SIAM, 2023.
  * [11] Vincent Cohen-Addad.  A fast approximation scheme for low-dimensional _k_ -means.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 430–440. SIAM, 2018.
  * [12] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan.  Improved approximations for Euclidean _k_ -means and _k_ -median, via nested quasi-independent sets.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1621–1628. ACM, 2022.
  * [13] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic.  Near-linear time approximation schemes for clustering in doubling metrics.  J. ACM, 68(6):44:1–44:34, 2021.
  * [14] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li.  Tight FPT approximations for k-median and k-means.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [15] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  On approximability of clustering problems without candidate centers.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2635–2648, 2021.
  * [16] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  Johnson coverage hypothesis: Inapproximability of k-means and k-median in $\mathscr{l}$${}_{\mbox{p}}$-metrics.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 1493–1530. SIAM, 2022.
  * [17] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu.  Local search yields approximation schemes for $k$-means and $k$-median in Euclidean and minor-free metrics.  SIAM Journal on Computing, 48(2):644–667, 2019.
  * [18] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  Improved coresets and sublinear algorithms for power means in Euclidean spaces.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 21085–21098, 2021.
  * [19] Anne Driemel, Amer Krivosija, and Christian Sohler.  Clustering time series under the Fréchet distance.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 766–785. SIAM, 2016.
  * [20] Anne Driemel, André Nusser, Jeff M. Phillips, and Ioannis Psarros.  The VC dimension of metric balls under Fréchet and Hausdorff distances.  Discret. Comput. Geom., 66(4):1351–1381, 2021.
  * [21] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 569–578. ACM, 2011.
  * [22] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for $k$-means, PCA, and projective clustering.  SIAM Journal on Computing, 49(3):601–657, 2020.
  * [23] Daniel Ferguson and François G. Meyer.  Computation of the sample Fréchet mean for sets of large graphs with applications to regression.  In Proceedings of the 2022 SIAM International Conference on Data Mining, SDM 2022, pages 379–387, 2022.
  * [24] Maurice Fréchet.  Les éléments aléatoires de nature quelconque dans un espace distancié.  Annales de L’Institut Henri Poincaré, 10(4):215–310, 1948.
  * [25] Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Rakesh Venkat.  A refined approximation for Euclidean k-means.  Inf. Process. Lett., 176:106251, 2022.
  * [26] Sudipto Guha and Samir Khuller.  Greedy strikes back: Improved facility location algorithms.  J. Algorithms, 31(1):228–248, 1999.
  * [27] Sariel Har-peled.  Geometric Approximation Algorithms.  American Mathematical Society, 2011.
  * [28] Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 291–300. ACM, 2004.
  * [29] Piotr Indyk.  Sublinear time algorithms for metric space problems.  In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 428–434. ACM, 1999.
  * [30] Eric D. Kolaczyk, Lizhen Lin, Steven J. Rosenberg, Jie Xu, and Jackson Walters.  Averages of unlabeled networks: Geometric characterization and asymptotic behavior.  The Annals of Statistics, 48(1):514–538, 2020.
  * [31] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear-time approximation schemes for clustering problems in any dimensions.  J. ACM, 57(2):5:1–5:32, 2010.
  * [32] Jiří Matoušek.  Lectures on Discrete Geometry, volume 212 of Graduate texts in mathematics.  Springer, 2002.
  * [33] Nimrod Megiddo and Kenneth J. Supowit.  On the complexity of some common geometric location problems.  SIAM J. Comput., 13(1):182–196, 1984.
  * [34] François G. Meyer.  The Fréchet mean of inhomogeneous random graphs.  In Complex Networks & Their Applications X - Volume 1, Proceedings of the Tenth International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021, volume 1015 of Studies in Computational Intelligence, pages 207–219, 2021.
  * [35] Yuriy Mileyko, Sayan Mukherjee, and John Harer.  Probability measures on the space of persistence diagrams.  Inverse Problems, 27(12):124007, 2011.
  * [36] Abhinandan Nath and Erin Taylor.  $k$-median clustering under discrete Fréchet and Hausdorff distances.  J. Comput. Geom., 12:156–182, 2022.
  * [37] Christof Schötz.  The Fréchet Mean and Statistics in Non-Euclidean Spaces.  PhD thesis, Heidelberg University, The Faculty of Mathematics and Computer Science, 2021.
  * [38] Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, and John Harer.  Fréchet means for distributions of persistence diagrams.  Discret. Comput. Geom., 52(1):44–70, 2014.
  * [39] Antoine Vigneron.  Geometric optimization and sums of algebraic functions.  ACM Trans. Algorithms, 10(1):4:1–4:20, 2014.