Embedding into the rectilinear plane in optimal O*(n^2)

Details Embedding into the rectilinear plane in optimal O*(n^2) Embedding into the rectilinear plane in optimal O*(n^2)

2009-10-06

arxiv.org/abs/0910.1059v1

Theoretical Computer Science Volume 412, Issue 22 (2011), Pages 2425-2433

Computer Science

Computational Geometry

12 pages, 13 figures

Scientific paper

10.1016/j.tcs.2011.01.038

We present an optimal O*(n^2) time algorithm for deciding if a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l_1-metric. It improves the O*(n^2 log^2 n) time algorithm of J. Edmonds (2008). Together with some ingredients introduced by J. Edmonds, our algorithm uses the concept of tight span and the injectivity of the l_1-plane. A different O*(n^2) time algorithm was recently proposed by D. Eppstein (2009).

Affiliated with

Also associated with

No associations

Rating

Embedding into the rectilinear plane in optimal O*(n^2) 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 Embedding into the rectilinear plane in optimal O*(n^2), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Embedding into the rectilinear plane in optimal O*(n^2) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-358285