A counter example to a monotonicity property of k-d trees (Q789903)

In Commun. ACM 18, 509-517 (1975; Zbl 0306.68061) \textit{J. L. Bentley} introduced k-dimensional binary search trees (abbreviated k-d tree) as a data structure for storing multikey records. The k-d tree, as defined in this paper, is a binary tree in which all the records are stored at external nodes, while each internal node has a discriminator field (indicating one of the k keys), a partition value (key value for the key chosen by the discriminator) and pointers to the left and right sons. The defining property of a k-d tree is that for any internal node x, if m is the discriminator value and M the partition value at x, then all records (within the subtree rooted at x) with m-th key values smaller or equal to M are located in the left subtree of x, while all records with m-th key values greater than M belong to the right subtree. The authors present an algorithm, of the dynamic programming type, for constructing an optimum k-d tree; their algorithm runs in \(0(n^{2k+1})\) time and it takes \(0(n^{2k})\) space. Further, the authors formulate a generalized version of the monotonicity property for 1-dimensional optimum binary search trees [\textit{A. Itai}, SIAM J. Comput. 5, 9-18 (1976; Zbl 0328.68040); \textit{D. E. Knuth}, Acta Inf. 1, 14-25 (1971; Zbl 0233.68011)] and show that it does not hold in the general setting.