Computer Science – Computational Geometry
39 pages, 15 figures
We describe a data structure, a rectangular complex, that can be used to 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 x n distance matrix, when the tight span is homeomorphic to a subset of the plane, in time O(n^2), and to add a single point to a planar tight span in time O(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(n^2), and add a single point to the space and re-test whether it has such an embedding in time O(n).
Optimally fast incremental Manhattan plane embedding and planar tight span construction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.If you have personal experience with Optimally fast incremental Manhattan plane embedding and planar tight span construction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimally fast incremental Manhattan plane embedding and planar tight span construction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-131185