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!