Representations of an arbitrary set of vertices of an n-dimensional cube in terms of convex sets are compared with respect to their complexity. The notion of complexity used in the representations is based on the union, symmetric difference and ternary median operations. Convexity of a set of vertices refers to Hamming distance or, equivalently, to the intersection of cubes with supporting hyperplanes.

CEMAT - Center for Computational and Stochastic Mathematics