David Eppstein - Publications

• 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₁ plane.

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

Semi-automatically filtered from a common source file.