Any Monotone Boolean Function Can Be Realized by Interlocked Polygons
Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara · DSpace@MIT (Massachusetts Institute of Technology) · 2010
We show how to construct interlocked collections of simple polygons in the plane that fall apart upon removing certain combinations of pieces. Precisely, interior-disjoint simple planar polygons are interlocked if no subset can be separated arbitrarily far from the rest, moving each polygon as a rigid object as in a sliding-block puzzle. Removing a subset S of these polygons might keep them interlocked or free the polygons, allowing them to separate. Clearly freeing removal sets satisfy monotonicity: if S S [prime] and removing S frees the polygons, then so does S [prime]. In this paper, we show that any monotone Boolean function f on n variables can be described by m > n interlocked polygons: n of the m polygons represent the n variables, and removing a subset of these n polygons frees the remaining polygons if and only if f is 1 when the corresponding variables are 1.