zbMATH — the first resource for mathematics

Linear decision trees, subspace arrangements, and Möbius functions. (English) Zbl 0811.05070
A linear decision tree is a rooted ternary tree with a linear functional \(\ell_ \alpha\) attached to each interior node and leaves labelled YES or NO. The edges connecting an internal node to its three descendants are labelled with the symbols \(<\), \(=\), and \(>\). This model is used to test membership \(x \in P\) for a convex polyhedron \(P \subseteq R^ n\) by moving down the tree, at each node using the sign of \(\ell_ \alpha (x)\) to determine which edge to follow. Upon reaching a leaf, the question “is \(x \in P\)” is answered.
In this paper the authors give lower bounds on the number of YES and NO leaves in terms of the Betti numbers of \(R^ n\setminus P\). Then the theory of arrangements of convex sets (e.g. subspaces) and Möbius functions is used to give asymptotic lower bounds on the size and depth of linear decision trees for various sorting problems, such as the problem of determining, for a given set of \(n\) real numbers, whether some \(k\) of them are equal, or whether some \(k\) of them are pairwise distinct. The arguments involve specific calculation of Möbius functions for various subposets of the partition lattice. The resulting lower bounds are stronger than those derived earlier by the same authors and others.
Reviewer: M.J.Falk (Madison)

05E99 Algebraic combinatorics
06A07 Combinatorics of partially ordered sets
57N99 Topological manifolds
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
68P10 Searching and sorting
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90B50 Management decision making, including multiple objectives
Full Text: DOI