
arXiv: 1908.07668
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: 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. 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. 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.
Computational Geometry (cs.CG), FOS: Computer and information sciences, G.2.0, 52C26, FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Circle packings and discrete conformal geometry, Combinatorics (math.CO), conveyor belt, NP-complete
Computational Geometry (cs.CG), FOS: Computer and information sciences, G.2.0, 52C26, FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Circle packings and discrete conformal geometry, Combinatorics (math.CO), conveyor belt, NP-complete
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
