Sequential Euclidean tree construction with exponential memory: distributional performance and worst-case guarantees

Abstract

Let $p_0,p_1,\ldots,p_N$ be points of the unit ball of $\mathbb R^d$, processed in a prescribed order. We study the insertion cost $\sum_{i=1}^N\lVert p_i-x_{i-1}\rVert^\alpha$, where each $x_{i-1}$ is computed from the previously observed points. The input-order path is sensitive to the input distribution but can repeatedly pay the diameter under adversarial input. The center star has controlled worst-case scale but ignores the observed sequence. We compress the past into one point through $x_0=p_0$ and $x_i=\gamma x_{i-1}+(1-\gamma)p_i$, where $0\leq\gamma\leq1$. Thus $x_i$ is an exponentially weighted memory of the input, maintained with one $d$-dimensional point of working state. For independent uniform points, the stationary insertion length is nonincreasing in the usual stochastic order as $\gamma$ increases. If $d\geq2$ and $\alpha>0$, every optimal constant parameter for $N$ insertions satisfies $1-\gamma_N^*=\Theta(N^{-1/2})$. We determine its asymptotic constant and the resulting $\sqrt N$ correction, with explicit bounds in $d$ and $\alpha$. For $\alpha=1$, the leading expected tree length equals that of the center star and is strictly smaller than those of the endpoint constructions. For $\alpha=2$, the minimizer is unique for $N\geq2$, with $1-\gamma_N^*=N^{-1/2}-\tfrac12N^{-1}+O(N^{-3/2})$. For arbitrary input sequences and fixed $0\leq\gamma<1$, the largest asymptotic mean cost is $(2/(1+\gamma))^\alpha$ for $0<\alpha\leq3$, strictly below the path value when $\gamma>0$. Among fixed nonnegative weighting rules whose contributing points have the same average distance in the input order from the most recent point, exponential weighting is within a factor smaller than $1.161^\alpha$ of the best adversarial value in dimension at least two; this ratio tends to one as that average distance grows.