Geodesic
Existence and hardness of conveyor belts
Molly Baird1 ; Sara Billey2 ; Erik Demaine3 ; Martin Demaine3 ; David Eppstein4 ; Sándor Fekete5 ; Graham Gordon2 ; Sean Griffin6 ; Joseph Mitchell7 ; Joshua Swanson8
1Department of Applied Mathematics, University of Washington, Seattle, WA, USA
2Department of Mathematics, University of Washington, Seattle, WA, USA
3Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
4Computer Science Department, University of California, Irvine, CA, USA
5Department of Computer Science, TU Braunschweig, Germany
6Department of Mathematics, University of California, San Diego, CA, USA
7Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA
8University of California, San Diego
The electronic journal of combinatorics, Tome 27 (2020) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/9782
Classification : 52C26
Mots-clés : conveyor belt, NP-complete

Molly Baird  1   ; Sara Billey  2   ; Erik Demaine  3   ; Martin Demaine  3   ; David Eppstein  4   ; Sándor Fekete  5   ; Graham Gordon  2   ; Sean Griffin  6   ; Joseph Mitchell  7   ; Joshua Swanson  8

1 Department of Applied Mathematics, University of Washington, Seattle, WA, USA
2 Department of Mathematics, University of Washington, Seattle, WA, USA
3 Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
4 Computer Science Department, University of California, Irvine, CA, USA
5 Department of Computer Science, TU Braunschweig, Germany
6 Department of Mathematics, University of California, San Diego, CA, USA
7 Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA
8 University of California, San Diego 
@article{10_37236_9782,
     author = {Molly Baird and Sara Billey and Erik Demaine and Martin Demaine and David Eppstein and S\'andor Fekete and Graham Gordon and Sean Griffin and Joseph Mitchell and Joshua  Swanson},
     title = {Existence and hardness of conveyor belts},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/9782},
     zbl = {1451.52013},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9782/}
}
TY  - JOUR
AU  - Molly Baird
AU  - Sara Billey
AU  - Erik Demaine
AU  - Martin Demaine
AU  - David Eppstein
AU  - Sándor Fekete
AU  - Graham Gordon
AU  - Sean Griffin
AU  - Joseph Mitchell
AU  - Joshua  Swanson
TI  - Existence and hardness of conveyor belts
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9782/
DO  - 10.37236/9782
ID  - 10_37236_9782
ER  - 
%0 Journal Article
%A Molly Baird
%A Sara Billey
%A Erik Demaine
%A Martin Demaine
%A David Eppstein
%A Sándor Fekete
%A Graham Gordon
%A Sean Griffin
%A Joseph Mitchell
%A Joshua  Swanson
%T Existence and hardness of conveyor belts
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9782/
%R 10.37236/9782
%F 10_37236_9782
Molly Baird; Sara Billey; Erik Demaine; Martin Demaine; David Eppstein; Sándor Fekete; Graham Gordon; Sean Griffin; Joseph Mitchell; Joshua  Swanson. Existence and hardness of conveyor belts. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9782

Cité par Sources :