Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
From MaRDI portal
Publication:533893
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
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
- Unnamed Item
- 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
- Geometry of cuts and metrics