Existence and Hardness of Conveyor Belts

  • Molly Baird
  • Sara C. Billey
  • Erik D. Demaine
  • Martin L. Demaine
  • David Eppstein
  • Sándor Fekete
  • Graham Gordon
  • Sean Griffin
  • Joseph S.B. Mitchell
  • Joshua P. Swanson


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.
Article Number