Paper by Erik D. Demaine
- Molly Baird, Sara C. Billey, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, and Joshua P. Swanson, “Existence and Hardness of Conveyor Belts”, The Electronic Journal of Combinatorics, volume 27, number 4, 2020, Article P4.25.
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.
- This paper is also available from EJC.
- The paper is available in PDF (654k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 15, 2021 by