Any Monotone Function Is Realized by Interlocked Polygons
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 i...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
MDPI AG
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86068 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826190519270637568 |
|---|---|
| author | Demaine, Erik D. Demaine, Martin L. Uehara, Ryuhei |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Demaine, Martin L. Uehara, Ryuhei |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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 ƒ 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. |
| first_indexed | 2024-09-23T08:41:29Z |
| format | Article |
| id | mit-1721.1/86068 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:41:29Z |
| publishDate | 2014 |
| publisher | MDPI AG |
| record_format | dspace |
| spelling | mit-1721.1/860682022-09-23T13:52:48Z Any Monotone Function Is Realized by Interlocked Polygons Demaine, Erik D. Demaine, Martin L. Uehara, Ryuhei Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Martin L. 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 ƒ 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. 2014-04-07T18:03:30Z 2014-04-07T18:03:30Z 2012-03 2012-03 Article http://purl.org/eprint/type/JournalArticle 1999-4893 http://hdl.handle.net/1721.1/86068 Demaine, Erik D., Martin L. Demaine, and Ryuhei Uehara. “Any Monotone Function Is Realized by Interlocked Polygons.” Algorithms 5, no. 4 (March 19, 2012): 148–157. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.3390/a5010148 Algorithms Creative Commons Attribution http://creativecommons.org/licenses/by/3.0/ application/pdf MDPI AG MDPI |
| spellingShingle | Demaine, Erik D. Demaine, Martin L. Uehara, Ryuhei Any Monotone Function Is Realized by Interlocked Polygons |
| title | Any Monotone Function Is Realized by Interlocked Polygons |
| title_full | Any Monotone Function Is Realized by Interlocked Polygons |
| title_fullStr | Any Monotone Function Is Realized by Interlocked Polygons |
| title_full_unstemmed | Any Monotone Function Is Realized by Interlocked Polygons |
| title_short | Any Monotone Function Is Realized by Interlocked Polygons |
| title_sort | any monotone function is realized by interlocked polygons |
| url | http://hdl.handle.net/1721.1/86068 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd anymonotonefunctionisrealizedbyinterlockedpolygons AT demainemartinl anymonotonefunctionisrealizedbyinterlockedpolygons AT uehararyuhei anymonotonefunctionisrealizedbyinterlockedpolygons |