Any Monotone Function is Realized by Interlocked Polygons

IR

Abstract

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

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/10662

Journal

  • Algorithms

    Algorithms 5 (1), 148-157, 2012-03-19

    MDPI Publishing

Details 詳細情報について

  • CRID
    1050564287491765248
  • NII Article ID
    120004288201
  • ISSN
    19994893
  • Web Site
    http://hdl.handle.net/10119/10662
  • Text Lang
    en
  • Article Type
    journal article
  • Data Source
    • IRDB
    • CiNii Articles

Report a problem

Back to top