Classifying hyperplanes in hypercubes

O. Aichholzer and F. Aurenhammer

Abstract:

We consider hyperplanes spanned by vertices of the unit $d$-cube. We classify these hyperplanes by parallelism to coordinate axes, by symmetry of the $d$-cube vertices they avoid, as well as by so-called hull-honesty. (Hull-honest hyperplanes are those whose intersection figure with the $d$-cube coincides with the convex hull of the $d$-cube vertices they contain; they do not cut $d$-cube edges properly.) We describe relationships between these classes, and give the exact number of hull-honest hyperplanes, in general dimensions. An experimental enumeration of all spanned hyperplanes up to dimension eight showed us the intrinsic difficulty of developing a general enumeration scheme. Motivation for considering such hyperplanes stems from coding theory, from linear programming, and from the theory of machine learning.



Reference: O. Aichholzer and F. Aurenhammer. Classifying hyperplanes in hypercubes. In Proc. $10^{th}$ European Workshop on Computational Geometry CG '94, pages 53-57, Santander, Spain, 1994.