# Any Monotone Boolean Function Can Be Realized by Interlocked Polygons

• Published in 2010
In the collections
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 \subseteq S′$ and removing $S$ frees the polygons, then so does $S′$. 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.

### BibTeX entry

@article{AnyMonotoneBooleanFunctionCanBeRealizedByInterlockedPolygons,
title = {Any Monotone Boolean Function Can Be Realized by Interlocked Polygons},
abstract = {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 \subseteq S′$ and removing $S$ frees the polygons, then so does $S′$. 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.},
url = {http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/ http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/paper.pdf},
year = 2010,
author = {Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara},
comment = {},
urldate = {2018-01-08},
collections = {Basically computer science,Easily explained,Geometry,Fun maths facts}
}