Digital Partitions Encoding

Abstract

In this paper we are interested in problems related to the encoding of partitions of discrete sets in R n with the restriction to the partitions which can be realized by a number of hyperplanes. A particular attention is given to the partitions of subsets of a planar integer grid of a given size, which is a model for a binary picture of a given size.

An application of the used encoding method to the encoding of linear threshold functions is given, as well. It turns out, that the obtained O(n 2) code is asymptotically optimal with respect to the required memory space.