Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces

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^{\Theta(1/d)}$, and this holds even when $d = \Theta(\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.