**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 L

_{1}plane.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.