Embedding into the rectilinear plane in optimal O(n2) time

In this paper, we present an optimal O(n2) time algorithm for deciding whether a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l1-metric. It improves the O(n2log2n) time algorithm of Edmonds (2008) [9], . Together with some ingredients introduced by Edmonds, our algorithm uses the concept of tight span and the injectivity of the l1-plane. A different O(n2) time algorithm was recently proposed by Eppstein (2009) [10].