Among the non-parametric classification methods, the nearest neighbour classifier (NNC) holds a pre-eminent position. Given a training or sample set \({\mathcal {S}}\) the choice one needs to make is on the value of k and the distance function d to be employed. Towards improving the efficacy of an NNC, there are many works—both theoretical and empirical—that help in choosing a suitable value of k. However, works that deal with the appropriateness of a distance d for a given \({\mathcal {S}}\) are largely empirical. In this work, we address the following two posers for a given \({\mathcal {S}}\) : (1) How to identify a potentially appropriate distance d? (2) What qualities should an appropriate d possess? Our investigations show that every distance function d determines a landscape on the underlying data space and only if the class boundaries align with this landscape can this d be appropriate. In view of this, we construct a relational graph \({\mathcal {G}}_{{\mathcal {S}},d}\) , in fact, a poset, on the given \({\mathcal {S}}\) using d. With the help of \({\mathcal {G}}_{{\mathcal {S}},d}\) , we choose a \({\mathcal {T}} \subset {\mathcal {S}}\) to be used in a condensed-NN algorithm. Terming it the NEN algorithm, firstly, we show empirically that the training error of this NEN algorithm is reflective of the appropriateness of d. Towards providing a theoretical justification to our claims based on empiricism, we investigate the problem of classification in the setting of monometric spaces, wherein it emerges that the suitability of d is essentially related to the embeddability of \({\mathcal {G}}_{{\mathcal {S}},d}\) in the monometric space ( \({\mathcal {X}}, \preceq _d,d\) ).
