Embedding into the rectilinear plane in optimal O(n(2)) time
In this paper, we present an optimal O(n(2)) time algorithm for deciding whether 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 Edmonds (2008)[9]. Together with some ingredients introduced by 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 Eppstein (2009) [10]. (C) 2011 Elsevier B.V. All rights reserved.
embedding algorithm metric space computational geometry