Preclustering Algorithms for Imprecise Points

We study the problem of preclustering a set B of imprecise points in \({\mathbb {R}}^d\): we wish to cluster the regions specifying the potential locations of the points such that, no matter where the points are located within their regions, the resulting clustering approximates the optimal clustering for those locations. We consider k-center, k-median, and k-means clustering, and obtain the following results. Let \(B := \{b_1,\ldots ,b_n\}\) be a collection of disjoint balls in \({\mathbb {R}}^d\), where each ball \(b_i\) specifies the possible locations of an input point \(p_i\). A partition \(\mathcal {C}\) of B into subsets is called an \((f(k),\alpha )\)-preclustering (with respect to the specific k-clustering variant under consideration) if (i) \(\mathcal {C}\) consists of f(k) preclusters, and (ii) for any realization P of the points \(p_i\) inside their respective balls, the cost of the clustering on P induced by \(\mathcal {C}\) is at most \(\alpha \) times the cost of an optimal k-clustering on P. We call f(k) the size of the preclustering and we call \(\alpha \) its approximation ratio. We prove that, even in \({\mathbb {R}}^1\), one may need at least \(3k-3\) preclusters to obtain a bounded approximation ratio—this holds for the k-center, the k-median, and the k-means problem—and we present a (3k, 1) preclustering for the k-center problem in \({\mathbb {R}}^1\). We also present various preclusterings for balls in \({\mathbb {R}}^d\) with \(d\geqslant 2\), including a \((3k,\alpha )\)-preclustering with \(\alpha \approx 13.9\) for the k-center and the k-median problem, and \(\alpha \approx 193.9\) for the k-means problem.

1. The subscript \(\infty \) in \({\textsc {Opt}}_{\infty }\) refers to the fact that if \(d_i\) denotes the distance of point \(p_i\in P\) to its nearest center, then we are minimizing the norm of the vector \(\langle d_1,\ldots ,d_n\rangle \) in the \(\ell _{\infty }\)-metric. For k-median and k-means we are minimizing the norm in the \(\ell _1\)-metric and in the squared \(\ell _2\)-metric, respectively.

Authors and Affiliations

1. Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

   Mohammad Ali Abam & Sina Farahzad

2. Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands

   Mark de Berg

3. Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran

   Mir Omid Haji Mirsadeghi & Morteza Saghafian

Corresponding author

Correspondence to Mohammad Ali Abam.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Mark de Berg supported by the Netherlands’ Organisation for Scientific Research (NWO) under project networks (project no. 024.002.003).

A Generalizations of Lemmas 3 and 4

We present the generalizations of Lemmas 3 and 4 which are used in order to prove Theorem 7. Note that p can take any value between 1 and n/k.

Lemma 13

For any B-instance P the preclustering \(\mathcal {C}:= \{ \{b_1\}, \ldots , \{b_{(p-1)k} \},B_1,\ldots ,B_{k} \}\) computed by the generalized algorithm satisfies:

1. (i)

   \(\mathcal {C}{{\text {-}}\textsc {Cost}}_{\infty }(P) \leqslant {\textsc {Opt}}_{\infty }(P,k) + 2 \cdot {{\,\mathrm{radius}\,}}(b_{(p-1)k+1})\)

2. (ii)

   \(\mathcal {C}{{\text {-}}\textsc {Cost}}_1(P) \leqslant {\textsc {Opt}}_1(P,k) + 2 \sum _{j=(p-1)k+1}^n {{\,\mathrm{radius}\,}}(b_j)\)

3. (iii)

   \(\sqrt{\mathcal {C}{{\text {-}}\textsc {Cost}}_2(P)} \leqslant \sqrt{{\textsc {Opt}}_2(P,k)} + 2\sqrt{\sum _{j=(p-1)k+1}^n {{\,\mathrm{radius}\,}}(b_j)^2}\).

Proof

We first prove part (i) of the lemma. Let P be any B-instance, let \(p_j\in P\) denote the point inside \(b_j\), and let \(c_j\) be the center of \(b_j\). Recall that \(P_i\subset P\) is the subset of points in the instance corresponding to the precluster \(B_i\). Define \(P_{\mathrm {small}}:= \{ p_{(p-1)k+1},\ldots ,p_n\}\) to be the set of points from P in the small balls, and define \(C_{\mathrm {small}}:= \{ c_{(p-1)k+1},\ldots ,c_n\}\). Note that \(P_{\mathrm {small}}= P_1\cup \cdots \cup P_k\) and that

for all \(p_j\in P_{\mathrm {small}}\). We define the following sets of centroids:

• Let \(Q := \{q_1,\ldots .q_k\}\) be the set of centroids in an optimal k-center solution for the entire point set P. We have

  $$\begin{aligned} \max _{p_j\in P_{\mathrm {small}}} \; \min _{q_i\in Q} |p_j q_i| \leqslant \max _{p_j\in P} \min _{q_i\in Q} |p_j q_i| = {\textsc {Opt}}_{\infty }(P,k). \end{aligned}$$

  (8)

• Let \(Q' := \{q'_1,\ldots ,q'_k\}\) be the set of centroids in the optimal k-center clustering on \(C_{\mathrm {small}}\) used in Step 2 of the algorithm. Thus

  $$\begin{aligned} \max _{c_i\in C_{\mathrm {small}}} \min _{q'_j \in Q'} |c_i q'_j| = {\textsc {Opt}}_{\infty }(C_{\mathrm {small}},k) \leqslant \max _{c_i\in C_{\mathrm {small}}} \min _{q_j \in Q} |c_i q_j|. \end{aligned}$$

  (9)

• Let \(Q'' := \{q''_1,\ldots ,q''_k\}\), where \(q''_i\) is the optimal centroid for \(P_i\). Note that for all \(P_i\) we have

  $$\begin{aligned} \max _{p_j\in P_i}|p_j q''_i| \leqslant \max _{p_j\in P_i}|p_j q'_i|. \end{aligned}$$

  (10)

Since the total cost of the singleton preclusters is trivially zero, we have

To prove part (ii) of the lemma, which deals with the k-median problem, note that Inequality (2) still holds while Inequalities (3)–(5) hold if we replace the \(\max \)-operator by a summation. Part (ii) can thus be derived using a similar derivation as for part (i).

To prove part (iii), which deals with the k-means problem, we need to work with squared distances. Note that Inequality (2) still holds, while Inequalities (3)–(5) hold if we replace the max-operator with a summation and all distance values with their squared values. For squared distances the triangle inequality does not hold. Instead we use the triangle inequality for \(L_2\) norm, which is called Minkowsky Inequality. A similar computation as above can now be used to prove part (iii); we have

On the other hand

By adding up the above inequalities we conclude part (iii) of the lemma. \(\square \)

Lemma 14

Let \(r^p_d\) be the smallest possible radius of any ball that intersects p disjoint unit balls in \({\mathbb {R}}^d\). Then

1. (i)

   \({\textsc {Opt}}_{\infty }(P,k) \geqslant r^p_d \cdot {{\,\mathrm{radius}\,}}(b_{(p-1)k+1})\)

2. (ii)

   \({\textsc {Opt}}_1(P,k) \geqslant r^p_d \cdot \sum _{j=(p-1)k+1}^{n} {{\,\mathrm{radius}\,}}(b_j)\)

3. (iii)

   \({\textsc {Opt}}_2(P,k) \geqslant (r^p_d)^2 \cdot \sum _{j=(p-1)k+1}^{n} {{\,\mathrm{radius}\,}}(b_j)^2\)

Proof

For part (i) notice that by the Pigeonhole Principle an optimal clustering must have a cluster containing at least p points from \(\{p_1,\ldots ,p_{(p-1)k+1}\}\). The cost of this cluster is lower bounded by the radius of the smallest ball intersecting p balls of radius at least \(b_{(p-1)k+1}\), which is in turn lower bounded by \(r^p_d \cdot {{\,\mathrm{radius}\,}}(b_{(p-1)k+1})\).

For part (ii) let \(P_1, P_2, \ldots , P_k\) be the clusters in an optimal k-median clustering on P, and let \(q_i\) be the centroid of \(P_i\) in this clustering. Let \(B_i\) be the set of balls corresponding the points in \(P_i\). We claim that

where \(s_i\) is the sum of the radii of the \(p-1\) largest balls in \(B_i\). To show this, let \(b(q_i,r)\) be the ball of radius r centered at \(q_i\), let \(P_i(r) := \{ p_j\in P_i: b_j \cap b(q_i,r)\ne \emptyset \}\) be the set of points in \(P_i\) whose associated ball intersects \(b(q_i,r)\), and let \(B_i(r)\) be the corresponding set of balls. Since for sufficiently large r we have \(P_i = P_i(r)\), it suffices to show that for all \(r>0\) we have

where \(s_i(r)\) is the sum of the radii of the \(p-1\) largest balls in \(B_i(r)\). To prove this, consider this inequality as r increases from \(r=0\) to \(r=\infty \). As long as \(|P_i(0)|\leqslant 2\) the right-hand side is zero and so the inequality is obviously true. As we increase r further, \(b(q_i,r)\) starts intersecting more and more balls from \(B_i\). Consider what happens to the inequality when \(b(q_i,r)\) starts intersecting another ball \(b_\ell \in B_i\). Then \(p_\ell \) is added to \(P_i(r)\), so the left-hand side of the inequality increases by \(|p_\ell q_i|\), which is at least r. The right-hand side increases by at most \(r^p_d\) times the radius of the p-th largest ball in \(B_i(r)\). By definition of \(r^p_d\), if p balls intersect a ball of radius r then the smallest has radius at most \(r/r^p_d\). Hence, the right-hand side increases by at most r and the inequality remains true.

Recall that \(b_1,\ldots ,b_{(p-1)k}\) are the \((p-1)k\) largest balls in B. Hence, summing Inequality (11) over all clusters \(P_1,\ldots ,P_k\) gives

For part (iii) the same proof as (ii) works if we replace all distances with squared distances. \(\square \)

B Proof of Theorem 9 for the k-Means Problem

For the k-means problem, observe that it suffices to prove the lower bound for \(k=1\); for larger k we can simply copy the construction k times and put the copies sufficiently far from each other. Now for \(k=1\), let \(n=\frac{2^{2t+1}-2}{3}\) and for every \(1\leqslant i \leqslant t\) let \(B_i\) be the set of \(2^{2t-2i}\) tiny intervals all very close to the point \(2^{i-1}\) in \({\mathbb {R}}^1\). Also let \(B_{-i}\) be the set of \(2^{2t-2i}\) tiny intervals all very close to the point \(-2^{i-1}\). Consider B as the union of \(B_{-t},\cdots ,B_{-2},B_{-1},B_1,B_2,\cdots ,B_t\). It is not difficult to see that \({\textsc {Opt}}_2(B,1)=2t\cdot 2^{2t-2}\) (considering the origin as the center). On the other hand assume that we precluster B into f(1) preclusters, using \(q_1,q_2,\cdots ,q_{f(1)}\) as centers. For \(1 \leqslant i \leqslant t\), let \(I_i\) be an open interval of length \(2^{i-2}\) whose midpoint is \(2^{i-1}\) and let \(I_{-i}\) be an open interval of length \(2^{i-2}\) whose midpoint is \(-2^{i-1}\). Note that \(I_{-t},\cdots ,I_{-2},I_{-1},I_1,I_2,\cdots I_t\) are disjoint. Thus, at least \(2t-f(1)\) number of the intervals \(I_{-t},\cdots ,I_{-2},I_{-1},I_1,I_2,\cdots I_t\) are empty of a center. But when \(I_i\) (similarly \(I_{-i}\)) is empty of a center, this means the total cost for \(B_i\) (similarly \(B_{-i}\)) is at least \(2^{2t-2i}\cdot (2^{i-3})^2)=2^{2t-6}\). Therefore, the total cost for any preclustering of B into f(1) preclusters is at least \((2t-f(1))\cdot 2^{2t-6}\). For a \((f(1),\varepsilon )\)-preclustering we should have

which concludes \(f(1)=\varOmega (t)\).

One can easily generalize this example to any \({\mathbb {R}}^d\) by considering the balls with diameters as the intervals in B introduced above.

Reprints and permissions