Department of Mathematics

Combinatorics and Graph Theory

  •  Sara Billey, University of Washington
  •  Existence and hardness of conveyor belts
  •  04/14/2021
  •  3:00 PM - 3:50 PM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Bruce E Sagan (bsagan@msu.edu)

We will present the notion of a conveyor belt configuration on disjoint disks in the plane, which means a tight simple closed curve that touches the boundary of each disk. 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, possibly touched multiple times. We will present 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. Many open problems remain on this topic and we will share some of our favorites. This talk is based on joint work with Molly Baird, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, and Joshua P. Swanson.

 

Contact

Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science