Separating points by parallel hyperplanes-characterization problem

Abstract

This paper deals with partitions of a discrete set S of points in a d-dimensional space, by h parallel hyperplanes. Such partitions are in a direct correspondence with multilinear threshold functions which appear in the theory of neural networks and multivalued logic. The characterization (encoding) problem is studied. We show that a unique characterization (encoding) of such multilinear partitions of S = {0, 1,..., m -1}d is possible within O(h · d2 · log m) bit rate per encoded partition. The proposed characterization (code) consists of (d+1) · (h+1) discrete moments having the order no bigger than 1. The obtained bit rate is evaluated depending on the mutual relations between h; d, and m. The optimality is reached in some cases.