Finite cluster trees and geometric admissibility

Let $I$ be a nonempty finite totally ordered set, let $d\ge 1$, and assign a point ${\xi }_i\in {\mathbb{R}}^d$ to each $i\in I$. A cluster is a nonempty subset of $I$. For a cluster $\tau$, write $X_{\tau }=\{{\xi }_i:i\in \tau \}$, $\mathrm{diam}(\tau )={\max }_{i,j\in \tau }\mathrm{\parallel }{\xi }_i-{\xi }_j{\mathrm{\parallel }}_2$, and $\mathrm{dist}(\tau ,\sigma )={\min }_{i\in \tau ,j\in \sigma }\mathrm{\parallel }{\xi }_i-{\xi }_j{\mathrm{\parallel }}_2$. These extrema exist because the index sets are finite and nonempty; repeated geometric points are allowed.

A balanced cluster tree with leaf threshold $b$, where $1\le b\le \mathrm{\mid }I\mathrm{\mid }$, is the rooted binary tree whose root is $I$, whose children of an internal cluster $\tau$ are its first $\lfloor \mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}2\rfloor$ and last $\lceil \mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}2\rceil$ indices in the fixed order, and which stops splitting at clusters of size at most $b$. Its two children are disjoint and their union is $\tau$.

For the column side, let $J$ be a nonempty finite totally ordered set, assign points ${\zeta }_j\in {\mathbb{R}}^d$ for $j\in J$, and build its balanced cluster tree by the same rule with its own threshold $1\le b_J\le \mathrm{\mid }J\mathrm{\mid }$. Column clusters are nonempty subsets $\sigma \subseteq J$, with $X_{\sigma }=\{{\zeta }_j:j\in \sigma \}$ and $\mathrm{diam}(\sigma )={\max }_{j,j^{\mathrm{\prime }}\in \sigma }\mathrm{\parallel }{\zeta }_j-{\zeta }_{j^{\mathrm{\prime }}}{\mathrm{\parallel }}_2$. For a row cluster $\tau \subseteq I$ and a column cluster $\sigma \subseteq J$, set $\mathrm{dist}(\tau ,\sigma )={\min }_{i\in \tau ,j\in \sigma }\mathrm{\parallel }{\xi }_i-{\zeta }_j{\mathrm{\parallel }}_2$. Row and column roles distinguish the assignments even when the index sets overlap. In the square case with a common point assignment, take $J=I$ and ${\zeta }_i={\xi }_i$.

Fix an admissibility parameter $\eta >0$. A pair of clusters $(\tau ,\sigma )$ is admissible when $\mathrm{dist}(\tau ,\sigma )>0$ and $\mathrm{dist}(\tau ,\sigma )\ge \eta \max (\mathrm{diam}(\tau ),\mathrm{diam}(\sigma ))$. The strict positive-distance condition keeps coincident or intersecting clusters in the near field, including diagonal singleton blocks.

The block-cluster tree starts at $(I,J)$. It stops at a pair if that pair is admissible or if both clusters are leaves. Otherwise, if only one cluster is nonleaf, it splits that cluster. If both are nonleaf, it splits the cluster of larger cardinality; ties are resolved by splitting the row cluster. The children of a split are the corresponding child-cluster pairs. Its terminal pairs are called block-cluster leaves. Admissible leaves are far blocks; nonadmissible leaves, which have two leaf clusters, are near blocks.