Embedding into the rectilinear plane in optimal O*(n^2)
Preprint
Abstract
We present an optimal O*(n^2) time algorithm for deciding if a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l_1-metric. It improves the O*(n^2 log^2 n) time algorithm of J. Edmonds (2008). Together with some ingredients introduced by J. Edmonds, our algorithm uses the concept of tight span and the injectivity of the l_1-plane. A different O*(n^2) time algorithm was recently proposed by D. Eppstein (2009).Keywords
All Related Versions
- Version 1, 2009-10-06, ArXiv
- Published version: Theoretical Computer Science, 412 (22), 2425.
This publication has 7 references indexed in Scilit:
- Embedding into l ∞ 2 Is Easy, Embedding into l ∞ 3 Is NP-CompleteDiscrete & Computational Geometry, 2008
- Geometry of Cuts and Metrics1997
- Embedding metric spaces in the rectilinear plane: A six-point criterionDiscrete & Computational Geometry, 1996
- A bounded compactness theorem forL 1-embeddability of metric spaces in the planeDiscrete & Computational Geometry, 1992
- The cut cone, L1 embeddability, complexity, and multicommodity flowsNetworks, 1991
- Gated sets in metric spacesAequationes mathematicae, 1987
- Extension of uniformly continuous transformations and hyperconvex metric spacesPacific Journal of Mathematics, 1956