Tangram

Transformar o problema do tangram para um problema de decisão: Dado um conjunto de peças e um contorno, existe alguma configuração dessas peças (sem sobreposição) que forme este contorno?

Esse problema é NP?

Muito similar ao problema de 2D bin packing, mas ele também não é de decisão, e sim de minimização. Como foi provado que o bin packing é NP-hard?

O tangram também pode ser um problema de minimização (otimização) se enunciado da seguinte forma: Dado um contorno e um conjunto de peças, como arranjar essas peças tais que elas fiquem o mais próximo possível do contorno? (será?)

Talvez não seja possível fazer uma redução ao problema de 2D bin packing porque ele é enunciado para peças retangulares de mesmo tamanho. Muito mais específico que o problema do tangram. E se eu transformar as peças to tangram em triângulos, como já foi feito pra provar outras coisas (e.g. a existência de somente 13 formatos convexos)?

Se eu conseguir fazer o contorno com os triângulos, talvez eu tenha uma solução para as peças inteiras. Se não for possível, com certeza não haverá solução:

Solução para as peças inteiras => solução com os triângulos iguais

Só umas ideias….