2026-08-25T18:47:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27175 2026-08-25T13:18:16Z ddc:004 open_access

Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces Licht, Noam Newman, Ilan Rabinovich, Yuri online embedding metric embedding online algorithms design of algorithms 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 solid graphs, i.e., K₅, 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 ℝ² with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of K₅ 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 ℝ^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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Licht and Ilan Newman and Yuri Rabinovich 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.39 urn:nbn:de:0030-drops-271750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.39 eng https://creativecommons.org/licenses/by/4.0/legalcode