Moving coins

DOI10.1016/J.COMGEO.2005.06.005MaRDI QIDQ2489547zbMATH OpenOpenAlexFDO

Authors Manuel Abellanas, Sergey Bereg, Alfredo García Olaverri, David Rappaport, Ferran Hurtado, 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

collision free translationscombinatorial boundscomputational complexityconfigurationdirected graphHamilton pathmoving coins

Mathematics Subject Classification ID

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

Review text

The authors consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as nonoverlapping discs, and moves are defined as collision free translations, all in the Euclidean plane. The problem is motivated by measuring the difference between various configurations. Using a directed graph, authors obtain combinatorial bounds on the number of moves that are necessary and/or sufficient to move coins from one configuration to another. They also consider several decision problems related to coin moving, and obtain some results regarding their computational complexity.

Recommendations

• scientific article; zbMATH DE number 1944413
• Coins and cones
• Versatile Coins
• Coins with Arbitrary Weights
• Turning a coin over instead of tossing it
• The game of flipping coins
• The game of flipping coins

Cites work

• Efficient algorithms for line and curve segment intersection using restricted predicates
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1944413 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Reducing Multiple Object Motion Planning to Graph Searching
• The earth mover's distance as a metric for image retrieval
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two

Cited in

(16)

• Coins and cones
• On triangle cover contact graphs
• Realizability of graphs as triangle cover contact graphs
• Realizability of Graphs as Triangle Cover Contact Graphs
• On Reconfiguration of Disks in the Plane and Related Problems
• Space-aware reconfiguration
• SLIDING DISKS IN THE PLANE
• scientific article; zbMATH DE number 1944413 (Why is no real title available?)
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Space-aware reconfiguration
• On the parameterized complexity of motion planning for rectangular robots
• A minor-testing approach for coordinated motion planning with sliding robots
• On the parameterized complexity of motion planning for rectangular robots
• More on the one-dimensional sliding-coin puzzle
• Convex blocking and partial orders on the plane

Describes a project that uses

Uses Software

• EMD

This page was built for publication: Moving coins

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489547)