Any Monotone Boolean Function Can Be Realized by Interlocked Polygons
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
University of Manitoba
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62257 https://orcid.org/0000-0003-3803-5703 |
| Summary: | 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 [prime] and removing S frees
the polygons, then so does S [prime]. 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. |
|---|