Any monotone function is realized by interlocked polygons

DOI10.3390/A5010148MaRDI QIDQ1736502zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a5010148

Mathematics Subject Classification ID

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Interlocked open and closed linkages with few joints.
• Mathematical characterizations and computational complexity of anti-slide puzzles
• scientific article; zbMATH DE number 4062595
• Untangling a polygon
• scientific article; zbMATH DE number 2084274

Cited in

(3)

• Logic circuits from zero forcing
• Picture-hanging puzzles
• Mathematical characterizations and computational complexity of anti-slide puzzles

This page was built for publication: Any monotone function is realized by interlocked polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736502)