# 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.

## Other information

key
AnyMonotoneBooleanFunctionCanBeRealizedByInterlockedPolygons
type
article
2018-01-08
date_published
2010-07-11

### BibTeX entry

@article{AnyMonotoneBooleanFunctionCanBeRealizedByInterlockedPolygons,
key = {AnyMonotoneBooleanFunctionCanBeRealizedByInterlockedPolygons},
type = {article},
title = {Any Monotone Boolean Function Can Be Realized by Interlocked Polygons},
author = {Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara},
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.},
comment = {},
}