Any Monotone Function Is Realized by Interlocked Polygons

Algorithms

Erik D. Demaine¹  Martin L. Demaine¹ 

[1] ¹Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology, MA 02139,USA ²School of Information Science, Japan Advanced Institute of Science and Technology, Ishikawa 923-1292, Japan

关键词: computational complexity;    interlocked polygons;    monotone boolean function;    sliding block puzzle;   

DOI  :  10.3390/a5010148

来源: mdpi

【 摘 要 】

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 ƒ 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.

【 授权许可】

CC BY   
This is an open access article distributed under the Creative Commons Attribution License (CC BY) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.