Dissection with the Fewest Pieces is Hard, Even to Approximate

DOI10.1007/978-3-319-48532-4_4zbMath1425.68427arXiv1512.06706OpenAlexW2407252880MaRDI QIDQ2958085

Mikhail Rudoy, Martin L. Demaine, Jayson Lynch, Jeffrey Bosboom, Anak Yodpinyanee, Pasin Manurangsi, Erik D. Demaine

Publication date: 1 February 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.06706

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Dissections and valuations (Hilbert's third problem, etc.) (52B45)

Related Items (2)

Rectangle transformation problem ⋮ Dissection with the Fewest Pieces is Hard, Even to Approximate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• Dissection with the Fewest Pieces is Hard, Even to Approximate
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Meshes Preserving Minimum Feature Size
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Dissection with the Fewest Pieces is Hard, Even to Approximate