Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

This paper is also available from EJC.

Availability:

The paper is available in PDF (654k).

See information on file formats.

[Google Scholar search]