Optimally fast incremental Manhattan plane embedding and planar tight span construction

David Eppstein


We describe a data structure, a rectangular complex, that can be used represent hyperconvex metric spaces that have the same topology (although not necessarily the same distance function) as subsets of the plane. We show how to use this data structure to construct the tight span of a metric space given as an n×distance matrix, when the tight span is homeomorphic to a subset of the plane, in time O(n2), and to add a single point to a planar tight span in timeO(n). As an application of this construction, we show how to test whether a given finite metric space embeds isometrically into the Manhattan plane in time O(n2), and add a single point to the space and re-test whether it has such an embedding in time O(n).

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v2i1a8

ISSN: 1920-180X