Interesting Esoterica

Any Monotone Boolean Function Can Be Realized by Interlocked Polygons

Article by Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara
  • Published in 2010
  • Added on
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.

Links

Other information

key
AnyMonotoneBooleanFunctionCanBeRealizedByInterlockedPolygons
type
article
date_added
2018-01-08
date_published
2010-10-09

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 = {},
	date_added = {2018-01-08},
	date_published = {2010-10-09},
	urls = {http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/,http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/paper.pdf},
	collections = {Basically computer science,Easily explained,Geometry,Fun maths facts},
	url = {http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/ http://erikdemaine.org/papers/InterlockedPolygons{\_}CCCG2010/paper.pdf},
	year = 2010,
	urldate = {2018-01-08}
}