Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
From MaRDI portal
Publication:938314
DOI10.1007/s00454-008-9064-zzbMath1149.68075OpenAlexW1985603099MaRDI QIDQ938314
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
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
