Finite Metric Spaces and Partitions

Notes 42 · 15-minute mathematical summary

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign · Fall 2026

Metrics and distortion

\[d:X\times X\to[0,\infty),\qquad |X|=n,\] \[d(x,y)=0\iff x=y,\quad d(x,y)=d(y,x),\quad d(x,z)\leq d(x,y)+d(y,z).\] \[B(x,r)=\{y:d(x,y)<r\},\qquad \operatorname{diam}(S)=\max_{x,y\in S}d(x,y).\]

\(f:X\to Y\) is \(K\)-bi-Lipschitz if some \(C>0\) satisfies \[\frac C K d_X(x,y)\leq d_Y(f(x),f(y))\leq C d_X(x,y).\] Distortion is the least such \(K\); \(C\)-Lipschitz requires only the upper bound.

CKR random partition

Independently sample a uniform permutation \(\pi=(z_1,\ldots,z_n)\) and \[R\sim\operatorname{Unif}[\Delta/4,\Delta/2].\] Set \[C_{z_i}=B(z_i,R)\setminus\bigcup_{h<i}B(z_h,R),\qquad P=\{C_{z_i}:C_{z_i}\ne\varnothing\}.\] Every point goes to its first eligible center; \(P(x)\) is its cluster.

For \(u,v\in C_z\), \(d(u,v)\leq d(u,z)+d(z,v)<2R\leq\Delta\). Thus \(\operatorname{diam}(C_z)\leq\Delta\) deterministically.

FRT partition lemma

For \(x\in X\), \(0<t\leq\Delta/8\), let \[a=|B(x,\Delta/8)|,\qquad b=|B(x,\Delta)|.\] Then \[\boxed{\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln\frac ba.}\] In particular, since \(1\leq a\leq b\leq n\), \[\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t\ln n}{\Delta}.\]

FRT proof I: fixed order and possible centers

Let \(B=B(x,t)\). Order the fixed set \(W=B(x,\Delta)\) as \[d(x,w_1)\leq\cdots\leq d(x,w_b).\] Use fixed tie-breaking. For a sampled radius, set \[A_R=\{w:d(x,w)<R+t\}\subseteq W,\] since \(R+t\leq5\Delta/8<\Delta\).

If \(B(w,R)\) meets \(B\), then \(d(x,w)<R+t\) by the triangle inequality. Thus every center that can claim a point of \(B\) belongs to \(A_R\).

FRT proof II: a cut needs a boundary witness

Let \(q\) be the first point of \(A_R\) in \(\pi\). If \(d(x,q)\leq R-t\), then \[d(q,z)\leq d(q,x)+d(x,z)<R\qquad(z\in B).\] No earlier center touches \(B\), so \(B\subseteq C_q=P(x)\). Consequently a cut implies \[R-t<d(x,q)<R+t.\]

If \(q=w_k\), a cut implies \(R\in I_k=[d(x,w_k)-t,d(x,w_k)+t]\). Also \(k>a\), since for \(k\leq a\), \[d(x,w_k)+t<\Delta/4\leq R.\]

FRT proof III: the two probability factors

The interval length is \(2t\), hence \[\Pr[R\in I_k]\leq\frac{2t}{\Delta/4}=\frac{8t}{\Delta}.\] If \(q=w_k\), every \(w_1,\ldots,w_k\) belongs to \(A_R\); \(w_k\) must be first among them. \[\Pr[w_k\text{ first among }w_1,\ldots,w_k]=\frac1k.\]

Define \(A_k=\{R\in I_k\}\cap\{w_k\text{ first among }w_1,\ldots,w_k\}\). The radius and permutation are independent, so \[\Pr[A_k]\leq\frac{8t}{\Delta k}.\]

FRT proof IV: union bound and harmonic sum

\[\{B(x,t)\nsubseteq P(x)\}\subseteq\bigcup_{k=a+1}^{b}A_k.\] Therefore \[ \begin{aligned} \Pr[B(x,t)\nsubseteq P(x)] &\leq\sum_{k=a+1}^{b}\frac{8t}{\Delta k}\\ &\leq\frac{8t}{\Delta}\int_a^b\frac{du}{u}\\ &=\boxed{\frac{8t}{\Delta}\ln\frac ba}. \end{aligned} \]

FRT consequence: constant-probability padding

For \(n\geq2\), \(\phi>0\), take \[\phi/4<\Delta\leq\phi/2,\qquad \rho=\frac{\phi}{64\ln n}.\] Then \(\rho\leq\Delta/8\), and \[\Pr[B(x,\rho)\nsubseteq P(x)] \leq\frac{8\rho\ln n}{\Delta}=\frac{\phi}{8\Delta}\leq\frac12.\]

The local bound retains \(\ln(b/a)\) for the tree analysis; the global bound \(\ln n\) suffices for the Euclidean construction.

Random HSTs

An HST has leaf set \(X\), labels \(\Delta_v=0\) exactly at leaves, and \[d_T(x,y)=\Delta_{\operatorname{lca}(x,y)}.\] A \(2\)-HST satisfies \(\Delta_u\leq\Delta_v/2\) for each child \(u\) of \(v\). The notes recursively partition each set \(S\) at scale \(\operatorname{diam}(S)/2\).

Tree theorem stated in the notes: a random noncontracting \(2\)-HST satisfies \[d(x,y)\leq d_T(x,y),\qquad \mathbb E[d_T(x,y)]\leq24\ln n\,d(x,y).\] The proof mechanism is telescoping local growth: \(\sum_i\ln(n_i/n_{i-3})\leq3\ln n\).

\(k\)-median via the random tree

\[\operatorname{cost}_d(C)=\sum_{p\in X}\min_{c\in C}d(p,c),\qquad |C|=k.\] Let \(C^*\) be optimal for \(d\), \(C_T\) optimal for \(d_T\), and \(c^*(p)\in\arg\min_{c\in C^*}d(p,c)\). Then \[\operatorname{cost}_d(C_T)\leq\operatorname{cost}_{d_T}(C_T) \leq\operatorname{cost}_{d_T}(C^*)\leq\sum_p d_T(p,c^*(p)).\]

\[\mathbb E[\operatorname{cost}_d(C_T)]\leq24\ln n\,\operatorname{OPT}_d.\] The notes give \(O(k^2n)\) time for exact \(k\)-median on an HST, and a polynomial-time expected \(O(\log n)\) approximation on the original metric.

Distance-to-set coordinates

For \(\varnothing\ne Y\subseteq X\), let \(f(x)=d(x,Y)\). If \(y'\in Y\) is nearest to \(y\), \[f(x)\leq d(x,y')\leq d(x,y)+f(y).\] By symmetry, \[\boxed{|f(x)-f(y)|\leq d(x,y).}\]

Bounded spread: construction

Normalize \(\min_{x\ne y}d(x,y)=1\); let \(\Phi=\operatorname{diam}(X)\). \[\alpha=1+\lceil\lg\Phi\rceil,\quad\beta=\lceil640\ln n\rceil, \quad r_i=2^{i-2}\ (1\leq i\leq\alpha).\] Independently sample diameter-\(r_i\) partitions \(P_{i,j}\), \(1\leq j\leq\beta\). Let \(V_{i,j}\) be the union of clusters selected by independent fair coins.

\[f_{i,j}(x)=d(x,X\setminus V_{i,j}),\qquad F(x)=(f_{i,j}(x))_{i,j}.\] If \(V_{i,j}=X\), set \(f_{i,j}\equiv0\). Then \(F:X\to\mathbb R^{\alpha\beta}\) and \[\|F(x)-F(y)\|_2\leq\sqrt{\alpha\beta}\,d(x,y).\]

Bounded spread: one successful trial

Fix \(\phi=d(x,y)>0\) and \(\phi/4<r_u\leq\phi/2\). Then \(P_{u,j}(x)\ne P_{u,j}(y)\). For \(\rho=\phi/(64\ln n)\), FRT gives \[\Pr[B(x,\rho)\subseteq P_{u,j}(x)]\geq1/2.\] With \(x\)’s cluster selected and \(y\)’s unselected, define \[E_j=\{B(x,\rho)\subseteq P_{u,j}(x),\ x\in V_{u,j},\ y\notin V_{u,j}\}.\]

Condition on the partition; the two coins are independent: \[\Pr[E_j]\geq\frac18,\qquad E_j\Longrightarrow f_{u,j}(x)\geq\rho,\quad f_{u,j}(y)=0.\]

Bounded spread: amplify separation

\[Z=\sum_{j=1}^{\beta}\mathbf1[E_j],\qquad\mu=\mathbb E[Z]\geq\beta/8.\] Independence across trials and the notes’ Chernoff bound give \[\Pr[Z<\beta/16]\leq e^{-\mu/8}\leq e^{-\beta/64}\leq n^{-10}.\] Thus, for this pair with probability at least \(1-n^{-10}\), \[\|F(x)-F(y)\|_2\geq\rho\sqrt{\beta/16} =\frac{\sqrt\beta}{256\ln n}\,d(x,y).\]

Bounded spread: dimension and distortion

Let \(G=(256\ln n/\sqrt\beta)F\). With failure probability less than \(n^{-8}\), simultaneously for all pairs, \[d(x,y)\leq\|G(x)-G(y)\|_2\leq256\sqrt\alpha\ln n\,d(x,y).\] The failure bound is \(\binom n2n^{-10}<n^{-8}\).

\[\dim G=O((1+\ln\Phi)\ln n),\qquad \operatorname{distortion}(G)=O(\sqrt{1+\ln\Phi}\,\ln n).\] For \(\Phi\geq2\), these match the notes’ stated \(O(\ln\Phi\ln n)\) and \(O(\sqrt{\ln\Phi}\ln n)\) bounds.

Unbounded spread: the proposed scale reduction

At scale \(r_i\), join pairs with \(d(x,y)\leq r_i/n^2\). Each connected component has diameter at most \(r_i/n\). The notes propose snapping components and capping coordinates at \(2r_i\). For \(\phi=d(x,y)\), the intended scale split is \[r_i>\phi n^2,\qquad \phi/n^2\leq r_i\leq\phi n^2, \qquad r_i<\phi/n^2.\] The middle range has \(O(\log n)\) scales; the last gives a geometric tail.

Proof gap in the notes: \(d_i(C,C')=\min_{x\in C,y\in C'}d(x,y)\) need not be a metric. The “Partition induced metric” exercise warns about this. The scale reduction above is an outline, not a complete proof as written.

Euclidean embedding results stated in the notes

Low quality Bourgain theorem: every \(n\)-point metric embeds into \(\mathbb R^{n-1}\) with distortion \(O(\log^{3/2}n)\).

A finite Euclidean image of \(n\) points has affine dimension at most \(n-1\). The notes state that Johnson–Lindenstrauss further reduces the dimension to \(O(\log n)\).

The introductory results also state:

  • Bourgain: distortion \(O(\log n)\) into Euclidean space.
  • Johnson–Lindenstrauss: distortion \(1+\varepsilon\) into \(\mathbb R^{O(\varepsilon^{-2}\log n)}\) for \(n\) Euclidean points.

These stronger results are stated here, not proved by the preceding outline.

Essential bounds

Partition: \(\operatorname{diam}(C)\leq\Delta\) and \[\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln\frac{|B(x,\Delta)|}{|B(x,\Delta/8)|}.\] Tree: \(d_T\geq d\) and \(\mathbb E[d_T(x,y)]\leq24\ln n\,d(x,y)\).

Clustering: \(\mathbb E[\operatorname{cost}_d(C_T)]\leq24\ln n\,\operatorname{OPT}_d\).

Bounded spread: \(\alpha\beta\) coordinates, \[\frac{\sqrt\beta}{256\ln n}\,d(x,y) \leq\|F(x)-F(y)\|_2\leq\sqrt{\alpha\beta}\,d(x,y).\] FRT supplies the protected ball that makes the lower bound possible.