Paper by Erik D. Demaine
- 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.
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.
- The paper is 4 pages.
- 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.
These pages are generated automagically from a
Last updated March 15, 2019 by