# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 4 Same Cluster Queries
### Small-Radius and Same-Cluster Queries  
Observe that Corollary 1 says that, if two points are _not_ in the same cluster, then their distance must be larger than \((\gamma-1)\) times the distance of one point to its optimal centroid. This condition does not automatically give a same-cluster query because it requires the knowledge of the optimal centroids, and it does not give an 'if and only if\" characterization. As we show below, under some additional assumptions, we can obtain a _characterization_ for two points being in the same cluster which does not involve the optimal centroids (see the next definition and lemma). This in turn implies that we can build a same-cluster query. **Definition 6** (\(\gamma\)-radius optimal clusters). : _Let \(d_{\max}^{(centroid)}\) be the maximum radius of the clusters in the optimal solution, that is, \(d_{\max}^{(centroid)}=\max_{x\in X}d(x,c_{i(x)}^{*})\) where \(c_{i(x)}^{*}\) is the centroid, the cluster containing \(x\) in the optimal solution. We say that a \(\gamma\)-perturbation-stable metric space \((X,d)\) has \(\gamma\)-radius optimal clusters if_  
\[2d_{\max}^{(centroid)}\leq(\gamma-1)d_{\min}^{(X)}\]  
_where \(d_{\min}^{(X)}=\min_{x\
eq y}d(x,y)\) is the minimum distance between two points._  
**Lemma 9** (same cluster condition). : _For any \(\gamma\)-perturbation-stable metric space \((X,d)\) which has \(\gamma\)-radius optimal clusters, with \(\gamma\geq 2\), the following holds. For every \(x,y\in X\),_  
\[d(x,y)\leq(\gamma-1)d_{\min}^{(X)}\qquad\qquad\Leftrightarrow\qquad\qquad x,y\in C_{i}^{*}\text{ for some }i\,\]  
_where \(C_{1}^{*},\ldots,C_{k}^{*}\) is the optimal solution._  
Proof. : We first prove the \((\Rightarrow)\) direction:  
\[d(x,y)\leq(\gamma-1)d_{\min}^{(X)}\Rightarrow d(x,y)\leq(\gamma-1)d(x,c_{i(x )}^{*})\Rightarrow y\in C_{i(x)}^{*}\,\]  
where \(C_{i(x)}^{*}\) and \(c_{i(x)}^{*}\) are the cluster and the centroid of \(x\) in the optimal solution, respectively, and the second implication is given by the contrapositive of Corollary 1. In order to prove the other direction \((\Leftarrow)\), consider arbitrary \(x\) and \(y\) in the same cluster with centroid \(c^{*}\) and observe that  
\[d(x,y)\leq d(x,c^{*})+d(y,c^{*})\leq\frac{d_{\min}^{(X)}(\gamma-1)}{2}+\frac{ d_{\min}^{(X)}(\gamma-1)}{2}=d_{\min}^{(X)}(\gamma-1)\,\]  
where the first inequality is by triangle inequality (metric space) and the second by the \(\gamma\)-radius optimal clusters assumption (Definition 6). Implementing a Same-Cluster Query  
According to Lemma 9, our same-cluster query, upon inputting two points \(x\) and \(y\), is simply checking whether \(d(x,y)\leq(\gamma-1)d_{\min}^{(X)}\) holds. We are now in a position to construct our same cluster query. In order to do so, we shall allow more general queries to compare pairwise distances multiplied by _scalars_, that is,  
\[O_{H}^{(\alpha)}(e_{1},e_{2})= \begin{cases}+1&\text{if }d(e_{1})>\alpha d(e_{2}) \\ -1&\text{otherwise}\end{cases}  \tag{6}\]  
for any two pairs of points \(e_{1}=(x_{1},y_{1})\) and \(e_{1}=(x_{2},y_{2})\). The cheap but erroneous counterpart \(O_{L}^{(\alpha)}(\cdot)\) is defined similarly, and its answers are wrong with the same probability \(p\leq 1/16\) as in our oracle \(O_{L}(\cdot)\). Observe that we can check whether \(d(x,y)\leq(\gamma-1)d_{\min}^{(X)}\) by one call to the above oracle with \(e_{1}=(x,y)\) and \(e_{\min}=\arg\min_{x^{\prime}\
eq y^{\prime}}d(x^{\prime},y^{\prime})\) being from the pair of points at a minimal distance, \(d_{\min}^{(X)}=d(e_{\min})\). Lemma 9 thus implies the following:  
**Lemma 10**. : _For every \(\gamma\)-perturbation-stable metric space \((X,d)\) which has \(\gamma\)-radius optimal clusters, \(\gamma\geq 2\), the following query_  
\[SCQ_{H}^{(\gamma)}(x,y):=O_{H}^{(\gamma-1)}((x,y),e_{\min})\]  
_is an exact same-cluster query, where \(e_{\min}=\arg\min_{x^{\prime}\
eq y^{\prime}}d(x^{\prime},y^{\prime})\).