Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, which means a tight simple closed curve that touches the boundary of each disk, possibly multiple times. We prove three main results: 1. For unit disks whose cen...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
The Electronic Journal of Combinatorics
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128809 |
| _version_ | 1826200374020669440 |
|---|---|
| author | Demaine, Erik D Demaine, Martin L |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Demaine, Martin L |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, which means a tight simple closed curve that touches the boundary of each disk, possibly multiple times. We prove three main results: 1. For unit disks whose centers are both x-monotone and y-monotone, or whose centers have x-coordinates that differ by at least two units, a conveyor belt always exists and can be found efficiently. 2. It is NP-complete to determine whether disks of arbitrary radii have a conveyor belt, and it remains NP-complete when we constrain the belt to touch disks exactly once. 3. Any disjoint set of n disks of arbitrary radii can be augmented by O(n) “guide” disks so that the augmented system has a conveyor belt touching each disk exactly once, answering a conjecture of Demaine, Demaine, and Palop. |
| first_indexed | 2024-09-23T11:35:42Z |
| format | Article |
| id | mit-1721.1/128809 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:35:42Z |
| publishDate | 2020 |
| publisher | The Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/1288092022-10-01T04:39:39Z Existence and hardness of conveyor belts Demaine, Erik D Demaine, Martin L Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, which means a tight simple closed curve that touches the boundary of each disk, possibly multiple times. We prove three main results: 1. For unit disks whose centers are both x-monotone and y-monotone, or whose centers have x-coordinates that differ by at least two units, a conveyor belt always exists and can be found efficiently. 2. It is NP-complete to determine whether disks of arbitrary radii have a conveyor belt, and it remains NP-complete when we constrain the belt to touch disks exactly once. 3. Any disjoint set of n disks of arbitrary radii can be augmented by O(n) “guide” disks so that the augmented system has a conveyor belt touching each disk exactly once, answering a conjecture of Demaine, Demaine, and Palop. 2020-12-11T13:59:31Z 2020-12-11T13:59:31Z 2020-10 2020-08 2020-12-09T16:42:23Z Article http://purl.org/eprint/type/JournalArticle 1097-1440 https://hdl.handle.net/1721.1/128809 Baird, Molly et al. “Existence and hardness of conveyor belts.” Electronic Journal of Combinatorics, 24, 7 (October 2020): P4.25 © 2020 The Author(s) en 10.37236/9782 Electronic Journal of Combinatorics Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics |
| spellingShingle | Demaine, Erik D Demaine, Martin L Existence and hardness of conveyor belts |
| title | Existence and hardness of conveyor belts |
| title_full | Existence and hardness of conveyor belts |
| title_fullStr | Existence and hardness of conveyor belts |
| title_full_unstemmed | Existence and hardness of conveyor belts |
| title_short | Existence and hardness of conveyor belts |
| title_sort | existence and hardness of conveyor belts |
| url | https://hdl.handle.net/1721.1/128809 |
| work_keys_str_mv | AT demaineerikd existenceandhardnessofconveyorbelts AT demainemartinl existenceandhardnessofconveyorbelts |