Embedding into the rectilinear plane in optimal \(O(n^{2})\) time

DOI10.1016/j.tcs.2011.01.038zbMath1216.68313OpenAlexW1992755708MaRDI QIDQ533893

Victor Chepoi, Yann Vaxès, Nicolas Catusse

Publication date: 10 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.038

zbMATH Keywords

algorithmembeddingmetric spacecomputational geometry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance geometry (51K99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Searching for realizations of finite metric spaces in tight spans

Cites Work

• Unnamed Item
• Extension of uniformly continuous transformations and hyperconvex metric spaces
• Gated sets in metric spaces
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• A bounded compactness theorem for \(L^ 1\)-embeddability of metric spaces in the plane
• Embedding metric spaces in the rectilinear plane: a six-point criterion
• Six theorems about injective metric spaces
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Embedding into the rectilinear grid
• Geometry of cuts and metrics