Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete

DOI10.1007/s00454-008-9064-zzbMath1149.68075OpenAlexW1985603099MaRDI QIDQ938314

Jeff Edmonds

Publication date: 19 August 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9064-z

zbMATH Keywords

AlgorithmNP-completeMetric spaceEmbeddingMöbius

Mathematics Subject Classification ID

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

Related Items (4)

Optimal Embedding into Star Metrics ⋮ The complexity of LSH feasibility ⋮ An alternative approach to distance geometry using \(L^\infty\) distances ⋮ Embedding into the rectilinear plane in optimal \(O(n^{2})\) time

Cites Work

• Unnamed Item
• Unnamed Item
• A bounded compactness theorem for \(L^ 1\)-embeddability of metric spaces in the plane
• Embedding into rectilinear spaces
• Embedding metric spaces in the rectilinear plane: a six-point criterion
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Embedding into the rectilinear grid
• Geometry of cuts and metrics

This page was built for publication: Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete