**Reference**:- Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara, “Any Monotone Boolean Function Can Be Realized by Interlocked Polygons”, in
*Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)*, Winnipeg, Manitoba, Canada, August 9–11, 2010, pages 139–142. **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*⊆*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. **Length**:- The paper is 4 pages.
**Availability**:- The paper is available in PDF (296k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- InterlockedPolygons_Algorithms (Any Monotone Boolean Function Can Be Realized by Interlocked Polygons)
**Related webpages**:- Interlocked Polygons

See also other papers by Erik Demaine.

Last updated March 9, 2018 by Erik Demaine.