Non-partitionable point sets (Q1058137)

Records in a database can be considered as points in a space whose dimension corresponds to the number of data fields. Let \(S\) be a finite set of \(n\) points in \(d\)-dimensional space. \(S\) is \(\alpha(n)\)-partitionable if there exists a set of mutually intersecting hyperplanes that divide \(d\)-space into \(2^ d\) open regions, no \(2^ d-1\) of which together contain more than \(\alpha(n)\) points of \(S\). It has been proved that every set in 2-space is \(3/4n\)-partitionable and every set in 3-space is \(23/24n\)-partitionable. The author has proved that there exist sets \(S\) of arbitrary cardinality in \(d\)-space, \(d\geq 5\), for which \(d^ 2+1\) open regions together contain at least \(n-d^ 2\) points of \(S\) in any partition of \(d\) intersecting hyperplanes, and that at least \(2^ d-d^ 2-1\) open regions contain no points of \(S\). It follows that the powerful balanced quad and oct-trees may not be generalized to balanced \(2^ d\)-trees in dimensions greater than or equal to 5.