Wooden geometric puzzles: Design and hardness proofs

DOI10.1007/S00224-008-9104-3MaRDI QIDQ2272190zbMATH OpenOpenAlexWikidataFDO

Authors Helmut Alt, Gerard Tel, Hans L. Bodlaender, Marc Van Kreveld, Günter Rote

Publication date 6 August 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-008-9104-3

zbMATH Keywords

complexitygeometric puzzlespartition

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Wooden Geometric Puzzles: Design and Hardness Proofs
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• Symmetric assembly puzzles are hard, beyond a few pieces
• Symmetric assembly puzzles are hard, beyond a few pieces
• Tatamibari is NP-complete

Cites work

• scientific article; zbMATH DE number 3596617 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1834637 (Why is no real title available?)
• Puzzles, art, and magic with algorithms
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• Tetris is Hard, Even to Approximate
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(4)

• Symmetric assembly puzzles are hard, beyond a few pieces
• Symmetric assembly puzzles are hard, beyond a few pieces
• Computational complexity of cast puzzles
• Wooden Geometric Puzzles: Design and Hardness Proofs

This page was built for publication: Wooden geometric puzzles: Design and hardness proofs

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