Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces
2026-07-12 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors studied how to map spaces where distances matter (metric spaces) into flat spaces like a plane or higher-dimensional spaces, when data points come in one by one and an opponent tries to make this hard. They showed that for a special graph called K5, you can embed it into 2D space with manageable distortion, disproving earlier beliefs. They also found that certain tree-like metrics can be embedded into higher dimensions almost as well as if you knew all points in advance, which is surprising since usually doing this online is much harder. These findings help connect complex metric structures to simpler Euclidean spaces more efficiently than before.
online embeddingmetric spaceEuclidean spacedistortionadaptive adversaryK5 graphtree metricsultrametricsHST (Hierarchically Separated Trees)offline vs online algorithms
Authors
Noam Licht, Ilan Newman, Yuri Rabinovich
Abstract
We study online embeddings of metric spaces into Euclidean spaces of a constant dimension $d>1$, against an adaptive adversary. While the case of $d=1$ is well understood, for higher dimensions little is known. In particular, even for $d=2$ it remains unknown whether the worst-case distortion grows exponentially with the number of exposed points, as it does in the case for the line, or whether it is polynomial, as in the case for unbounded $d$. Our first result is about fixed {\em solid} graphs, i.e., $K_5$, whose edges are solid intervals, equipped with the shortest-path metric. We show that if the input points arrive from such a metric space, they can indeed be online-embedded into ${\mathbb R}^2$ with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of $K_5$ into the plane could be exploited for establishing exponential lower bounds. The second results is about online embeddings of tree metrics of a certain type, including, e.g., ultrametrics and HST's. Somewhat surprisingly, we show that for metrics from this class the worst-case online embedding into ${\mathbb R}^d$ is not much worse that the offline embedding, both being $n^{Θ(1/d)}$, and this holds even when $d = Θ(\log n)$. This is in a stark contrast to the more common situation where the online-offline gap is typically huge, and even exponential. This result allows us to transfer results about probabilistic embeddings of metrics into HST's to low-dimensional Euclidean spaces, in an almost optimal possible manner.