License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.1
URN: urn:nbn:de:0030-drops-66241
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6624/
Go to the corresponding LIPIcs Volume Portal

Backurs, Arturs ; Sidiropoulos, Anastasios

Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces

pdf-format:
LIPIcs-APPROX-RANDOM-2016-1.pdf (0.5 MB)

Abstract

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

BibTeX - Entry

@InProceedings{backurs_et_al:LIPIcs:2016:6624,
  author =	{Arturs Backurs and Anastasios Sidiropoulos},
  title =	{{Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6624},
  URN =		{urn:nbn:de:0030-drops-66241},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.1},
  annote =	{Keywords: metric embeddings, Hausdorff metric, distortion, dimension}
}

Keywords: metric embeddings, Hausdorff metric, distortion, dimension
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI