2026-07-21T12:18:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6624 2024-03-06T10:38:32Z ddc:004 open_access

Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces Backurs, Arturs Sidiropoulos, Anastasios metric embeddings Hausdorff metric distortion dimension We show that the Hausdorff metric over constant-size pointsets in constant-dimensional Euclidean space admits an embedding into constant-dimensional l_{infinity} space with constant distortion. More specifically for any s,d>=1, we obtain an embedding of the Hausdorff metric over pointsets of size s in d-dimensional Euclidean space, into l_{\infinity}^{s^{O(s+d)}} with distortion s^{O(s+d)}. We remark that any metric space M admits an isometric embedding into l_{infinity} with dimension proportional to the size of M. In contrast, we obtain an embedding of a space of infinite size into constant-dimensional l_{infinity}. We further improve the distortion and dimension trade-offs by considering probabilistic embeddings of the snowflake version of the Hausdorff metric. For the case of pointsets of size s in the real line of bounded resolution, we obtain a probabilistic embedding into l_1^{O(s*log(s()} with distortion O(s). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arturs Backurs and Anastasios Sidiropoulos 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.1 urn:nbn:de:0030-drops-66241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.1 eng https://creativecommons.org/licenses/by/3.0/legalcode