|
Abstract : |
Abstract. We describe two methods for estimating the size and depth of decision trees where a linear test is performed at each node. Both methods are applied to the question of deciding, by a linear decision tree, whether given n real numbers, some k of them are equal. We show that the minimum depth of a linear decision tree for this problem is (nlog(n/k)). The upper bound is easy; the lower bound can be established for k = O(n 1/4?) by a volume argument; for the whole range, however, our proof is more complicated and it involves the use of some topology as well as the theory of Mbius functions. 1. Introduction. Let P be a set in IR n. Given a point x, we want to test if x ? P. Our model, |
