Existence and hardness of conveyor belts
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 cen...
Main Authors: | Demaine, Erik D, Demaine, Martin L |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | English |
Published: |
The Electronic Journal of Combinatorics
2020
|
Online Access: | https://hdl.handle.net/1721.1/128809 |
Similar Items
-
UNO is hard, even for a single player
by: Demaine, Erik D., et al.
Published: (2011) -
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect
by: Demaine, Erik D
Published: (2020) -
Rigid foldability is NP-hard
by: Demaine, Erik D, et al.
Published: (2020) -
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
by: Bosboom, Jeffrey, et al.
Published: (2021) -
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
by: Demaine, Erik D, et al.
Published: (2019)