Optimally fast incremental Manhattan plane embedding and planar tight span construction

Details Optimally fast incremental Manhattan plane embedding and planar tight span construction Optimally fast incremental Manhattan plane embedding and planar tight span construction

2009-09-10

arxiv.org/abs/0909.1866v2

Journal of Computational Geometry 2(1):144-182, 2011

Computer Science

Computational Geometry

39 pages, 15 figures

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131185