互锁多边形可实现任何单调布尔函数(2010)

2021-01-04 12:38:44

我们展示了如何在平面上构造互锁的简单多边形集合,这些平面在移除某些组合后会散开。如果没有子集可以任意地与其余部分分开,则内部不相交的简单平面多边形将互锁,将每个多边形移动为刚性 移除这些多边形的子集S可能会使它们互锁或使这些多边形自由,从而允许它们分离。明确释放的移除集满足单调性:如果S⊆S'并移除S释放了多边形,那么 在本文中,我们证明了任何单调布尔函数形式的变量都可以用m>来描述。 n个互锁的多边形:m个多边形中的n个代表n个变量,并且仅当当对应变量为1且f为1时,移除这n个多边形的子集才能释放其余多边形