A Lower Bound for the Closest Pair Problem
C. E. Chronaki, E. P. Markatos · 1991
We prove a lower bound on the number of distance queries necessary to solve the closest pair problem in a set of binary strings. We show that given a set of \ell^d binary strings of length 2 \cdot \ell \cdot d+1, at least \Omega (\ell ^{d+1}) pairwise distance queries have to be made by any decision tree algorithm that finds the pair of closest strings. .pp In the course of proving this lower bound, we examine a graph theoretic problem related to lattice graphs. The nodes and edges of a lattice graph correspond to points and links of a d-dimensional grid. We consider the problem of distinguishing a lattice graph \cal L _{d,\ell} of dimension d with \ell^d nodes from its subgraph \cal L'' _{d,\ell}; the latter is induced by removing the edges of a single node across one dimension. We derive a lower bound of \Omega (\ell^{d+1}) on the number of adjacency matrix queries made by any decision-tree algorithm that solves the problem.