## 3 Triangular Calculus  
The algorithms in this paper support a large family of distance and nondistance functions. To exactly define this family, and their dependency on both the approximation factors and running times of the algorithms, we need to introduce the notion of \(\rho\)-metric that generalizes the definition \((P,\text{dist})\) of a metric space. For a point \(p\in P\) and a set \(X\subseteq P\), we define \(f(p,X)=\min_{x\in X}f(p,x)\). The minimum or sum over an empty set is defined to be zero. **Definition 1** (\(\rho\)-metric). : _Let \(\rho\geq 1\), \(P\) be a finite set and \(f:P^{2}\to[0,\infty)\) be a symmetric function such that \(f(p,p)=0\) for every \(p\in P\). The pair \((P,f)\) is a \(\rho\)-metric if for every \(x,y,z\in P\) the following \"approximated\" triangle inequality holds:_  
\[f(x,z)\leq\rho\big{(}f(x,y)+f(y,z)\big{)}. \tag{1}\]  
For example, metric space \((P,\text{dist})\) is a \(\rho\)-metric for \(\rho=1\). If we define \(f(x,y)=(\text{dist}(x,y))^{2}\), as in the \(k\)-means case, it is easy to prove (1) for \(\rho=2\). The approximated triangle inequality also holds for sets as follows. **Lemma 1**. : (See 6.1 of [59]) _Let \((P,f)\) be a \(\rho\)-metric. Then, for every pair of points \(q,x\in P\) and a subset \(X\subseteq P\) we have_  
\[f(x,X)\leq\rho(f(q,x)+f(q,X)). \tag{2}\]  
Proof. : For every \(p,q\in P\), and a center \(x_{q}\in X\) that is closest to \(q\), i.e., \(f(q,X)=f(q,x_{q})\), we have  
\[f(x,X)=\min_{p\in X}f(x,p)\leq f(x,x_{q})\leq\rho(f(q,x)+f(q,x_{q}))=\rho(f(q, x)+f(q,X)).\]  
Our generalization of the \(k\)-means++ algorithm for other distance functions needs only the above definition of \(\rho\)-metric. However, to improve the approximation bounds for the case of \(k\)-means with \(m\) outliers in Section 5, we introduce the following variant of the triangle inequality. **Definition 2** (\((\rho,\phi,\varepsilon)\) metric). : _Let \((P,f)\) be a \(\rho\)-metric. For \(\phi,\varepsilon>0\), the pair \((P,f)\) is a \((\rho,\phi,\varepsilon)\)-metric if for every \(x,y,z\in P\) we have_  
\[f(x,z)-f(y,z)\leq\phi f(x,y)+\varepsilon f(x,z). \tag{3}\]  
For example, for a metric space \((P,\text{dist})\) the inequality holds by the triangle inequality for \(\phi=1\) and every \(\varepsilon\geq 0\). For squared distance, we have \(\phi=O(1/\varepsilon)\) for every \(\varepsilon>0\); see [18]. The generalization for sets is a bit more involved as follows. **Lemma 2**. : _Let \((P,f)\) be a \((\rho,\phi,\varepsilon)\)-metric. For every set \(Z\subseteq P\) we have_  
\[|f(x,Z)-f(y,Z)|\leq(\phi+\varepsilon\rho)f(x,y)+\varepsilon\rho\min\left\{f(x,Z),f(y,Z)\right\}.\]  
Proof. : Let \(z_{x},z_{y}\in Z\) such that \(f(x,Z)=f(x,z_{x})\) and \(f(y,Z)=f(y,z_{y})\). Without loss of generality, we assume \(f(y,Z)\leq f(x,Z)\). We have  
\[ \begin{split}|f(x,Z)-f(y,Z)|=f(x,Z)-f(y,Z)&=f(x, z_{x})-f(y,z_{y})\leq f(x,z_{y})-f(y,z_{y})\\ &\leq\phi f(x,y)+\varepsilon f(x,z_{y}),\end{split}  \tag{4}\]  
where the last inequality is by (3). The last term is bounded by \(f(x,z_{y})\leq f(y,z_{y})+\phi f(x,y)+\varepsilon f(x,z_{y})\) via Definition 2, but this bound is useless for the case \(\varepsilon>1\). Instead, we use (1) to obtain  
\[f(x,z_{y})\leq\rho\big{(}f(x,y)+f(y,z_{y})\big{)}=\rho f(x,y)+\rho f(y,Z).\]  
Plugging the last inequality in (4) proves the case \(f(y,Z)\leq f(x,Z)\) as  
\[ \begin{split}|f(x,Z)-f(y,Z)|&\leq\phi f(x,y)+ \varepsilon(\rho f(x,y)+\rho f(y,Z))\\ &=(\phi+\varepsilon\rho)f(x,y)+\varepsilon\rho f(y,Z)=(\phi+ \varepsilon\rho)f(x,y)+\varepsilon\rho\min\left\{f(y,Z),f(x,Z)\right\}.\end{split} \]  
Any \(\rho\)-metric is also a \((\rho,\phi,\varepsilon)\)-metric for some other related constants as follows. **Lemma 3**. : _Let \((P,f)\) be a \(\rho\)-metric. Then \((P,f)\) is a \((\rho,\phi,\varepsilon)\)-metric, where \(\phi=\rho\) and \(\varepsilon=\rho-1\)._  
Proof. : Let \(x,y,z\in P\). We need to prove that  
\[f(x,z)-f(y,z)\leq\phi f(x,y)+\varepsilon f(x,z).\]  
Without loss of generality, \(f(x,z)>f(y,z)\), otherwise the claim is trivial.