David Eppstein - Publications

• Optimally fast incremental Manhattan plane embedding and planar tight span construction.
  D. Eppstein.
  arXiv:0909.1866.
  Journal of 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.