Any monotone function is realized by interlocked polygons
type: Item
instance of: scholarly article
title: Any monotone function is realized by interlocked polygons
zbMATH Open document ID: 1461.68241
author: Erik D. Demaine
author: Martin L. Demaine
author: Ryuhei Uehara
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: Suppose there is a collection of \(n\) simple polygons in the plane, none of which overlap each other. The polygons are \textit{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.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7042119
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a5010148
OpenAlex ID: W2055678622
DOI: 10.3390/A5010148
description: scientific article; zbMATH DE number 7042119