Optimally fast incremental Manhattan plane embedding and planar tight span construction

Computer Science – Computational Geometry

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-131185

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.