- Optimally fast incremental Manhattan plane embedding and planar
tight span construction.
D. Eppstein.
arXiv:0909.1866.
J. Computational Geometry 2 (1): 144–182, 2011.Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L1 plane.