David Eppstein – Publications

Publications with Sara Billey

• Existence and hardness of conveyor belts.
  M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
  arXiv:1908.07668.
  Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.

  A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.