|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/10662
|
| タイトル: | Any Monotone Function is Realized by Interlocked Polygons |
| 著者: | Demaine, Erik D.
Demaine, Martin L.
Uehara, Ryuhei |
| キーワード: | Computational Complexity
interlocked polygons
monotone Boolean function
sliding block puzzle |
| 発行日: | 2012-03-19 |
| 出版者: | MDPI Publishing |
| 誌名: | Algorithms |
| 巻: | 5 |
| 号: | 1 |
| 開始ページ: | 148 |
| 終了ページ: | 157 |
| DOI: | 10.3390/a5010148 |
| 抄録: | 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. |
| Rights: | © 2012 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/) |
| URI: | http://hdl.handle.net/10119/10662 |
| 資料タイプ: | publisher |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 17809.pdf | | 2189Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
