Embedding into the rectilinear plane in optimal O(n^2) time
DOI10.1016/J.TCS.2011.01.038zbMATH Open1216.68313OpenAlexW1992755708MaRDI QIDQ533893FDOQ533893
Authors: Nicolas Catusse, Victor Chepoi, Yann Vaxès 
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
Recommendations
- Embedding into the rectilinear grid
- Embedding into rectilinear spaces
- Optimally fast incremental Manhattan plane embedding and planar tight span construction
- Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
- Embedding metric spaces in the rectilinear plane: a six-point criterion
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance geometry (51K99)
Cites Work
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Six theorems about injective metric spaces
- Geometry of cuts and metrics
- Optimally fast incremental Manhattan plane embedding and planar tight span construction
- Extension of uniformly continuous transformations and hyperconvex metric spaces
- Gated sets in metric spaces
- The cut cone,L1 embeddability, complexity, and multicommodity flows
- Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
- 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
- Embedding into the rectilinear grid
Cited In (6)
- Algorithms for \(\ell_{1}\)-embeddability and related problems
- Searching for realizations of finite metric spaces in tight spans
- A new combinatorial approach to optimal embeddings of rectangles
- Optimally fast incremental Manhattan plane embedding and planar tight span construction
- Level Planar Embedding in Linear Time
- Embedding into the rectilinear grid
This page was built for publication: Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533893)
