Pedro Ivo Uchôa Serra Mendes de Castro

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

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 repe...