Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.37236/9782 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 27.0 | 4.0 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 10 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Baird Molly | 1 | 0 | 0.34 |
| Sara C. Billey | 2 | 32 | 7.46 |
| Erik D. Demaine | 3 | 4624 | 388.59 |
| Martin L. Demaine | 4 | 592 | 84.37 |
| David Eppstein | 5 | 4897 | 533.94 |
| Fekete Sándor | 6 | 0 | 0.34 |
| Gordon Graham | 7 | 0 | 0.34 |
| Griffin Sean | 8 | 0 | 0.34 |
| Joseph S.B. Mitchell | 9 | 4329 | 428.84 |
| Swanson Joshua P. | 10 | 0 | 0.34 |