Finite Metric Spaces and Partitions

Notes 42 · Full lecture · 75 minutes

Sariel Har-Peled

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

Today’s route

Random partitions preserve small neighborhoods with useful probability. The FRT partition lemma is the main tool of this lecture.

Topic Minutes
Metrics, distortion, and motivation 10
Partition construction and FRT lemma 35
Random trees and \(k\)-median 10
Euclidean embeddings 17
Recap and exercises 3

A finite metric space

\(X\) is a set of \(n\) points; \(d:X\times X\to[0,\infty)\) satisfies

\[ d(x,y)=0\iff x=y,\qquad d(x,y)=d(y,x), \] \[ \boxed{d(x,z)\leq d(x,y)+d(y,z).} \]

The triangle inequality will control both cluster diameters and cut probabilities.

Two representations

A finite metric can be specified by \(\binom n2\) pairwise distances: a complete weighted graph satisfying the triangle inequality.

A connected undirected graph with positive edge lengths gives the metric \[d_G(x,y)=\text{length of a shortest path from }x\text{ to }y.\] A sparse graph can represent its metric compactly.

Balls and diameter

We use open balls, as in the notes: \[B(x,r)=\{y\in X:d(x,y)<r\}.\] For a nonempty set \(C\subseteq X\), \[\operatorname{diam}(C)=\max_{u,v\in C}d(u,v).\]

A ball radius and a cluster diameter are different parameters. Two points in a radius-\(R\) ball can be almost \(2R\) apart.

Embeddings and distortion

For \(f:(X,d_X)\to(Y,d_Y)\), \(C\)-Lipschitz means \[d_Y(f(x),f(y))\leq C\,d_X(x,y).\] \(K\)-bi-Lipschitz means that some \(C>0\) satisfies \[\frac C K d_X(x,y)\leq d_Y(f(x),f(y))\leq C d_X(x,y).\]

The least such \(K\) is the distortion. A common scale factor is allowed.

Why distortion is necessary

In the unit-edge three-leaf star, \[d(s,a)=d(s,b)=d(s,c)=1,\qquad d(a,b)=d(b,c)=d(c,a)=2.\] The notes’ equilateral-triangle calculation gives \[\operatorname{distortion}(f)\geq \frac{2}{\sqrt3}>1.\]

The notes' equilateral triangle of side length two and its enclosing circle.

A simpler target: a hierarchical tree metric

The points are leaves of a rooted tree. Each node has a label \(\Delta_v\): \[\Delta_v=0\iff v\text{ is a leaf},\qquad \Delta_u\leq\Delta_v\quad(u\text{ child of }v).\] \[\boxed{d_T(x,y)=\Delta_{\operatorname{lca}(x,y)}.}\]

For a \(k\)-HST, \(\Delta_u\leq\Delta_v/k\) along every parent–child edge.

Why use randomness?

For the unit-edge cycle \(C_n\), a noncontracting HST embedding has \[\operatorname{distortion}(f)\geq\lfloor n/2\rfloor.\] Some adjacent cycle vertices separate at the top relevant tree split.

The notes instead seek a distribution of trees: \[d_T(x,y)\geq d(x,y),\qquad \mathbb E[d_T(x,y)]\leq O(\log n)\,d(x,y).\] The expectation is for each fixed pair.

Algorithmic motivation: \(k\)-median

Choose \(C\subseteq X\), \(|C|=k\), minimizing \[\operatorname{cost}_d(C)=\sum_{p\in X}d(p,C),\qquad d(p,C)=\min_{c\in C}d(p,c).\]

The notes give an \(O(k^2n)\) dynamic program on an HST. Embed into a random HST, solve there, and return its centers in \(X\).

Partitions: the notation

\[P=\{C_1,\ldots,C_m\},\qquad X=\bigcup_{i=1}^m C_i,\qquad C_i\cap C_j=\varnothing\ (i\ne j).\] \(P(x)\) denotes the unique cluster containing \(x\).

We want small cluster diameters, while keeping a small ball \(B(x,t)\) inside \(P(x)\) with high probability.

CKR construction: two random choices

Fix a diameter scale \(\Delta>0\) (the notes use dyadic scales).

  1. Choose a uniformly random permutation \(\pi\) of \(X\).
  2. Independently choose \(R\sim\operatorname{Unif}[\Delta/4,\Delta/2]\).

There is one shared radius for this partition. The permutation decides which center claims a point first.

Assign a point to its first eligible center

Write \(\pi=(z_1,\ldots,z_n)\). Then \[C_{z_i}=B(z_i,R)\setminus\bigcup_{h<i}B(z_h,R).\] Discard empty clusters.

Every point is assigned: \(x\in B(x,R)\). Assignments are unique: the first eligible center wins.

Scooping out the first balls

Early balls in the notes' CKR partition illustration.

Only the part of a new ball not already claimed becomes a new cluster.

Later centers claim only what remains

A later stage of the notes' CKR partition, with overlapping balls and assigned regions.

The radius remains fixed throughout this partition.

The resulting partition

The completed partition from the notes.

Clusters need not themselves be balls.

Diameter bound: the first use of triangle inequality

For \(u,v\in C_z\subseteq B(z,R)\), \[d(u,v)\leq d(u,z)+d(z,v)<2R\leq\Delta.\] Therefore \[\boxed{\operatorname{diam}(C_z)\leq\Delta.}\]

This conclusion holds for every permutation and every allowed radius.

FRT partition lemma

Fix \(x\in X\) and \(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.}\] Every cluster has diameter at most \(\Delta\).

Read the bound before proving it

\[\underbrace{\frac{8t}{\Delta}}_{\text{relative radius}} \quad\cdot\quad \underbrace{\ln\frac{|B(x,\Delta)|}{|B(x,\Delta/8)|}}_{\text{local growth}}.\]

Since \(1\leq a\leq b\leq n\), \[\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln n.\] The sharper local ratio is what the tree analysis uses.

Fix the ball; expose the randomness in stages

Keep \(x,t,\Delta\) and the input metric fixed. Write \[B=B(x,t).\] First condition on the value of \(R\); the permutation remains uniform.

We will use a fixed distance order for the proof. This order is different from the random permutation \(\pi\).

Which centers could touch the ball?

If \(B(w,R)\cap B\ne\varnothing\), choose \(z\) in the intersection: \[d(x,w)\leq d(x,z)+d(z,w)<t+R.\] Thus every center that can affect \(B\) belongs to \[A_R=\{w\in X:d(x,w)<R+t\}.\]

Some centers in \(A_R\) might not actually touch \(B\). That is harmless.

All relevant centers lie in a fixed outer ball

\[R+t\leq\frac\Delta2+\frac\Delta8=\frac{5\Delta}{8}<\Delta.\] Therefore \[A_R\subseteq W:=B(x,\Delta),\qquad |W|=b.\]

Order this fixed set by distance from \(x\): \[d(x,w_1)\leq d(x,w_2)\leq\cdots\leq d(x,w_b).\] Break equal-distance ties in any fixed way.

The first candidate can protect the entire ball

Let \(q\) be the first center of \(A_R\) in permutation order. If \(d(x,q)\leq R-t\), then for every \(z\in B\), \[d(q,z)\leq d(q,x)+d(x,z)<(R-t)+t=R.\]

No earlier center can touch \(B\). Hence \(B\subseteq C_q=P(x)\).

A cut forces the first candidate into the boundary band

Taking the contrapositive: \[B\nsubseteq P(x)\quad\Longrightarrow\quad R-t<d(x,q)<R+t.\] Equivalently, if \(q=w_k\), \[R\in I_k:=[d(x,w_k)-t,\ d(x,w_k)+t].\]

The interval has length \(2t\). This is where the random radius helps.

Three distance regimes

Centers at distance at most R minus t contain the protected ball; centers farther than R plus t cannot touch it; a possible cutting witness is in between.

These are triangle-inequality statements, valid in every metric. They do not assume Euclidean geometry or convexity.

The radius factor

\[R\sim\operatorname{Unif}[\Delta/4,\Delta/2],\qquad |[\Delta/4,\Delta/2]|=\Delta/4.\] For every fixed \(k\), \[\Pr[R\in I_k] =\frac{|I_k\cap[\Delta/4,\Delta/2]|}{\Delta/4} \leq\boxed{\frac{8t}{\Delta}}.\]

The intersection can only shorten the interval.

A short bad interval inside the sampling interval

The radius is sampled from an interval of length Delta over four. A given center's boundary interval has length two t.

\[\frac{\text{length of possible bad radii}}{\text{length of sampling interval}} \leq\frac{2t}{\Delta/4}=\frac{8t}{\Delta}.\]

Why the first \(a\) centers cannot be bad

For \(k\leq a\), \(d(x,w_k)<\Delta/8\). Since \(t\leq\Delta/8\), \[d(x,w_k)+t<\Delta/4\leq R.\] Such a center’s radius-\(R\) ball contains all of \(B\).

The witness of a cut must have rank \(k>a\). This is why the final logarithm starts at \(a\), rather than at \(1\).

The permutation factor

Suppose the first candidate \(q\) has distance rank \(k\). Then all of \(w_1,\ldots,w_k\) are in \(A_R\). Consequently \(w_k\) must appear first among these \(k\) points in \(\pi\).

Uniform permutation symmetry gives \[\boxed{\Pr[w_k\text{ is first among }w_1,\ldots,w_k]=\frac1k.}\]

Combine the two sources of randomness

Define the possible-witness event \[A_k=\{R\in I_k\}\cap \{w_k\text{ first among }w_1,\ldots,w_k\text{ in }\pi\}.\] The distance order and \(I_k\) are fixed, while \(R\) and \(\pi\) are independent: \[\Pr[A_k]\leq\frac{8t}{\Delta}\cdot\frac1k.\]

Cover every possible cut

If \(B\) is cut, its first candidate has some rank \(k>a\) and satisfies \(A_k\). Therefore \[\{B\nsubseteq P(x)\}\subseteq\bigcup_{k=a+1}^{b}A_k.\]

By the union bound, \[\Pr[B\nsubseteq P(x)] \leq\frac{8t}{\Delta}\sum_{k=a+1}^{b}\frac1k.\]

Turn the harmonic sum into local growth

For \(k\geq a+1\), \[\frac1k\leq\int_{k-1}^{k}\frac{du}{u}.\] Summing, \[\sum_{k=a+1}^{b}\frac1k \leq\int_a^b\frac{du}{u}=\ln b-\ln a=\boxed{\ln\frac ba}.\]

FRT proof: the complete chain

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

Random radius: \(8t/\Delta\). Random order: \(1/k\). Protected inner centers: start the sum at \(a+1\).

What if the neighborhood does not grow?

If \(B(x,\Delta/8)=B(x,\Delta)\), then \(a=b\) and \[\Pr[B(x,t)\nsubseteq P(x)]\leq0.\]

Every potentially relevant center is already close enough to contain \(B(x,t)\). The local ratio captures this protection exactly.

What each random choice accomplishes

The radius must fall into a short interval before a fixed center can be a boundary witness: \[\Pr[R\in I_k]\leq 8t/\Delta.\]

The center must also beat all \(k-1\) nearer candidates in the permutation: \[\Pr[\text{first among }k]=1/k.\]

A useful global version

For \(n\geq2\) and \(t\leq\Delta/8\), \[\boxed{\Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t\ln n}{\Delta}.}\] At the scale used later, choose \[\rho=\frac{\phi}{64\ln n},\qquad \frac\phi4<\Delta\leq\frac\phi2.\] Then the failure probability is at most \(1/2\).

FRT checkpoint

Reconstruct the proof from these four lines:

  1. A first center within \(R-t\) captures the whole ball.
  2. A bad first center forces \(R\in[d(x,w)-t,d(x,w)+t]\).
  3. A rank-\(k\) witness must be first among \(k\) fixed points.
  4. \(\sum_{k=a+1}^b1/k\leq\ln(b/a)\).

Two uses of the same padding bound

Random trees: keep the local growth ratio \(\ln(b/a)\). Across scales, logarithmic growth terms telescope.

Euclidean embeddings: use \(\ln(b/a)\leq\ln n\). A protected ball and independent cluster coins create a separating coordinate.

Building a random \(2\)-HST

For a current set \(S\):

  1. Give its root the label \(\operatorname{diam}(S)\).
  2. Partition \(S\) at diameter scale \(\operatorname{diam}(S)/2\).
  3. Recurse on each nonempty cluster; singletons become leaves.

Child labels are at most half the parent label. At the least common ancestor of \(x,y\), the label is at least \(d(x,y)\).

The tree-embedding guarantee stated in the notes

Every \(n\)-point metric admits a random noncontracting \(2\)-HST embedding with \[\boxed{\mathbb E[d_T(x,y)]\leq24\ln n\,d(x,y)}\] for each fixed pair \(x,y\).

This is an expected guarantee for each pair, not a claim that one sampled tree simultaneously has logarithmic distortion on every pair.

The tree proof’s telescoping mechanism

Write \(t=d(x,y)\) and \(n_i=|B(x,2^i)|\). The notes seek scale charges of the form \[2^i\cdot\frac{8t}{2^i}\ln\frac{n_i}{n_{i-3}}.\] The algebraic gain is \[\sum_{i=j}^{0}\ln\frac{n_i}{n_{i-3}}\leq3\ln n.\]

The ratio spans three dyadic levels: most logarithms cancel. This explains why the local FRT bound matters.

\(k\)-median: solve on the sampled tree

Let \(C^*\) be optimal for the original metric and let \(C_T\) be optimal for \(d_T\). For each \(p\), fix a nearest original center \(c^*(p)\in C^*\).

\[ \begin{aligned} \operatorname{cost}_d(C_T) &\leq\operatorname{cost}_{d_T}(C_T)\\ &\leq\operatorname{cost}_{d_T}(C^*)\\ &\leq\sum_{p\in X}d_T(p,c^*(p)). \end{aligned} \]

Expected approximation cost

By linearity of expectation and the tree theorem, \[ \begin{aligned} \mathbb E[\operatorname{cost}_d(C_T)] &\leq\sum_{p\in X}\mathbb E[d_T(p,c^*(p))]\\ &\leq24\ln n\sum_{p\in X}d(p,c^*(p))\\ &=24\ln n\,\operatorname{OPT}_d. \end{aligned} \]

The notes conclude a polynomial-time algorithm with expected \(O(\log n)\) approximation.

From partitions to Euclidean coordinates

At each scale, sample a partition and independently toss one fair coin per cluster. Let \(V\) be the union of clusters whose coins are tails.

A union of randomly selected clusters from the notes' partition illustration.

Distance to a set is nonexpansive

For a nonempty \(Y\subseteq X\), set \(f(x)=d(x,Y)\). If \(y'\in Y\) is nearest to \(y\), then \[f(x)\leq d(x,y')\leq d(x,y)+d(y,y')=d(x,y)+f(y).\] Swap \(x\) and \(y\): \[\boxed{|f(x)-f(y)|\leq d(x,y).}\]

Spread and the bounded-spread target

\[\Phi=\frac{\operatorname{diam}(X)}{\min_{x\ne y}d(x,y)}.\] Normalize the smallest distance to \(1\). Set \[\alpha=1+\lceil\lg\Phi\rceil,\qquad \beta=\lceil640\ln n\rceil.\]

The notes’ construction gives dimension \(\alpha\beta\) and distortion \[O(\sqrt\alpha\ln n).\] For \(\Phi\geq2\), these are \(O(\ln\Phi\ln n)\) and \(O(\sqrt{\ln\Phi}\ln n)\).

Sample independently at each scale

\[r_i=2^{i-2},\qquad 1\leq i\leq\alpha,\quad1\leq j\leq\beta.\] Sample a diameter-\(r_i\) partition \(P_{i,j}\) and its cluster coins. Let \(V_{i,j}\) be the union of tails clusters, and define \[f_{i,j}(x)=d(x,X\setminus V_{i,j}).\]

If \(V_{i,j}=X\), use the constant-zero coordinate. This convention makes every coordinate finite and nonexpansive.

Concatenate all coordinates

\[F(x)=\bigl(f_{1,1}(x),\ldots,f_{1,\beta}(x),\ldots, f_{\alpha,1}(x),\ldots,f_{\alpha,\beta}(x)\bigr).\] There are \(\alpha\beta\) coordinates, each nonexpansive. Hence \[\boxed{\|F(x)-F(y)\|_2\leq\sqrt{\alpha\beta}\,d(x,y).}\]

Choose the scale for one fixed pair

Fix \(x\ne y\), with \(\phi=d(x,y)\). Choose \(u\) so that \[r_u\leq\phi/2<2r_u,\qquad\text{thus }\phi/4<r_u\leq\phi/2.\] Since cluster diameters are at most \(r_u<\phi\), \(x\) and \(y\) lie in different clusters.

Set \(\rho=\phi/(64\ln n)\). The FRT lemma gives \[\Pr[B(x,\rho)\subseteq P_{u,j}(x)]\geq1/2.\]

A protected ball plus two cluster coins

Use the event \[E_j=\{B(x,\rho)\subseteq P_{u,j}(x),\ x\in V_{u,j},\ y\notin V_{u,j}\}.\] Conditioned on any partition, the distinct clusters of \(x,y\) have independent coins: \[\Pr[E_j]\geq\frac12\cdot\frac12\cdot\frac12=\frac18.\]

One successful coordinate separates the pair

On \(E_j\), the whole ball \(B(x,\rho)\) lies in \(V_{u,j}\), while \(y\) lies outside. Therefore \[f_{u,j}(x)\geq\rho,\qquad f_{u,j}(y)=0,\] \[|f_{u,j}(x)-f_{u,j}(y)|\geq\rho.\]

This is exactly where padding becomes a lower bound on an embedding distance.

Repetition: many successful coordinates

Let \(Z=\sum_{j=1}^{\beta}\mathbf1[E_j]\). The trials are independent and \[\mu=\mathbb E[Z]\geq\beta/8.\] The Chernoff estimate used in the notes gives \[\Pr[Z<\beta/16]\leq\Pr[Z<\mu/2] \leq e^{-\mu/8}\leq e^{-\beta/64}\leq n^{-10}.\]

Lower bound and rescaling

With probability at least \(1-n^{-10}\) for this pair, \[\|F(x)-F(y)\|_2\geq\rho\sqrt{\beta/16} =\frac{\sqrt\beta}{256\ln n}\,d(x,y).\] Set \(G=(256\ln n/\sqrt\beta)F\). Then \[d(x,y)\leq\|G(x)-G(y)\|_2 \leq256\sqrt\alpha\ln n\,d(x,y).\]

Make the guarantee simultaneous

There are \(\binom n2\) unordered pairs. A union bound gives \[\Pr[\text{some pair fails}]\leq\binom n2n^{-10}<n^{-8}.\]

The notes propose checking all pairwise distortions and restarting if necessary. Thus the bounded-spread construction succeeds with high probability.

Unbounded spread: the obstacle

The bounded-spread dimension depends on \(\ln\Phi\). With arbitrarily many scales, there are two problems:

  1. Too many coordinates.
  2. A pair can contribute to too many resolution blocks.

The notes propose ignoring very short distances at each scale and capping the coordinate values at \(2r_i\).

The proposed snapping step needs care

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 intercomponent distances \[d_i(C,C')=\min_{x\in C,\,y\in C'}d(x,y).\]

This minimum-distance formula need not satisfy the triangle inequality. The notes’ “Partition induced metric” exercise explicitly asks for a counterexample. Thus the subsequent argument is a proof outline, not a complete proof as written.

The intended scale accounting

For a fixed pair at distance \(\phi\), the notes organize the blocks as follows:

Scale Intended contribution
\(r_i>\phi n^2\) Identical coordinates
\(\phi/n^2\leq r_i\leq\phi n^2\) \(O(\log n)\) relevant scales
\(r_i<\phi/n^2\) Geometric tail, using the cap \(2r_i\)

The intended upper bound is \(O(\phi\sqrt{\beta\log n})\), leading to distortion \(O(\log^{3/2}n)\) with the earlier lower bound.

The Euclidean theorem stated in the notes

Low quality Bourgain theorem. Every \(n\)-point metric embeds into \(\mathbb R^{n-1}\) with distortion \[\boxed{O(\log^{3/2}n).}\] The notes also state that Johnson–Lindenstrauss reduces the dimension to \(O(\log n)\).

Once a finite Euclidean embedding is obtained, its \(n\) image points lie in an affine subspace of dimension at most \(n-1\), preserving all their distances.

What the partition lemma made possible

\[\operatorname{diam}(C)\leq\Delta,\qquad \Pr[B(x,t)\nsubseteq P(x)]\leq\frac{8t}{\Delta}\ln\frac ba.\]

For trees: local growth across scales.

For Euclidean coordinates: a protected ball, two cluster coins, and repetition.

For clustering: noncontraction plus a per-pair expected tree bound.

Exercises from the notes

Clustering for HST: obtain the \(O(k^2n)\) algorithm. Hint from the notes: transform to a binary tree, then use dynamic programming.

Partition induced metric: give a counterexample to the minimum-distance formula being a metric for an arbitrary partition.

Diameter via embeddings: use \(O(1/\sqrt\varepsilon)\) planar projections to obtain a \((1-\varepsilon)\) diameter approximation in \(O(n/\sqrt\varepsilon)\) time.