Separated block decomposition for vector subset sums

ID: separated-block-decomposition-for-vector-subset-sums

For Euclidean vectors of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with blocks of size . To extend a separated block by a vector , choose its member minimizing inner product with . The translated block together with remains separated, since . The untransformed block with removed remains separated too. Block sizes change from to , the same recurrence as a symmetric chain decomposition of a Boolean lattice. There are exactly nonempty blocks.

New to topics? Read the docs here!