Existence and hardness of conveyor belts (Q2209897)

Summary: 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: \begin{itemize} \item [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. \item [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. \item [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. \end{itemize}