Moving coins

DOI10.1016/j.comgeo.2005.06.005zbMath1098.65022OpenAlexW2914514102MaRDI QIDQ2489547

Sergey Bereg, Manuel Abellanas, David Rappaport, Alfredo García Olaverri, Ferran Hurtado, F. Javier Tejel

Publication date: 28 April 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2005.06.005

zbMATH Keywords

computational complexityconfigurationdirected graphHamilton pathcombinatorial boundscollision free translationsmoving coins

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Other designs, configurations (05B30) Complexity and performance of numerical algorithms (65Y20) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items

On Reconfiguration of Disks in the Plane and Related Problems, Space-aware reconfiguration, Realizability of Graphs as Triangle Cover Contact Graphs, Convex blocking and partial orders on the plane, On triangle cover contact graphs, Realizability of graphs as triangle cover contact graphs, SLIDING DISKS IN THE PLANE, Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch, More on the one-dimensional sliding-coin puzzle, Unnamed Item, Space-Aware Reconfiguration

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Efficient algorithms for line and curve segment intersection using restricted predicates
• The earth mover's distance as a metric for image retrieval
• Reducing Multiple Object Motion Planning to Graph Searching