Classifying hyperplanes in hypercubes

被引:16
作者
Aichholzer, O
Aurenhammer, F
机构
[1] Inst. for Theor. Computer Science, Graz University of Technology, A-8010 Graz
关键词
d-cube; hyperplane cuts; hyperplane enumeration;
D O I
10.1137/S089548019426348X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:225 / 232
页数:8
相关论文
共 25 条
  • [1] AICHHOLZER O, 1992, THESIS GRAZ U TECHNO
  • [2] COVERING THE CUBE BY AFFINE HYPERPLANES
    ALON, N
    FUREDI, Z
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1993, 14 (02) : 79 - 83
  • [3] CUBE SLICING IN RN
    BALL, K
    [J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1986, 97 (03) : 465 - 473
  • [4] BALL K, 1989, LECT NOTES MATH, V1376, P251
  • [5] Berlekamp E. R., 1968, ALGEBRAIC CODING THE
  • [6] Chakerian D., 1991, MATH MAG, V64, P219, DOI DOI 10.2307/2690829
  • [7] Coxeter H. S. M., 1963, REGULAR POLYTOPES
  • [8] Craigen Rob., 1990, J COMB MATH COMB COM, V8
  • [9] GRAY CODES AND PATHS ON THE N-CUBE
    GILBERT, EN
    [J]. BELL SYSTEM TECHNICAL JOURNAL, 1958, 37 (03): : 815 - 826
  • [10] ADDRESSING PROBLEM FOR LOOP SWITCHING
    GRAHAM, RL
    POLLAK, HO
    [J]. BELL SYSTEM TECHNICAL JOURNAL, 1971, 50 (08): : 2495 - +