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

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

Yann Vaxès, Victor Chepoi, 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

algorithm; embedding; metric space; computational geometry

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

51K99: Distance geometry

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• 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
• Geometry of cuts and metrics
• Unnamed Item
• Unnamed Item