Paper by Erik D. Demaine
- Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara, “Any Monotone Boolean Function Can Be Realized by Interlocked Polygons”, Algorithms, volume 5, number 1, March 2012, pages 148–157.
Suppose there is a collection of n simple polygons in the plane, none of
which overlap each other. The polygons are interlocked if no subset can
be separated arbitrarily far from the rest. It is natural to ask the
characterization of the subsets that makes the set of interlocked polygons
free (not interlocked). This abstracts the essence of a kind of sliding block
puzzle. We show that any monotone Boolean function f on n variables can be
described by m = O(n) interlocked polygons. We also show that the decision
problem that asks if given polygons are interlocked is PSPACE-complete.
- This paper is also available from MDPI (open access).
- The paper is 10 pages.
- The paper is available in PDF (2189k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- InterlockedPolygons_CCCG2010 (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 August 3, 2020 by