Mestrado — Matemática e Algoritmos das Dobras

Minha dissertação de mestrado no IME-USP, orientada pelo Prof. Dr. José Coelho de Pina Jr., sobre origami computacional — a área da ciência da computação que estuda algoritmos eficientes para problemas envolvendo dobras de papel.

O trabalho cobre três grandes temas:

Origami matemático — a relação entre construções geométricas com régua e compasso e construções com dobras. Com dobras é possível fazer construções impossíveis com régua e compasso, como a trissecção de um ângulo.
Complexidade computacional — a demonstração de que decidir se um diagrama de dobras pode ser dobrado de forma plana é NP-completo (teorema de Bern e Hayes). Inclui os teoremas de Maekawa e Kawasaki sobre condições necessárias para dobras planas.
O problema de dobrar e cortar — dado um polígono desenhado em uma folha de papel, é possível dobrá-la de modo que um único corte reto separe o polígono do resto do papel. O método de Bern, Demaine, Eppstein e Hayes é descrito e implementado.

A implementação do algoritmo de dobrar e cortar foi feita em Java e está disponível como o projeto open source JOrigami.

Downloads

Dissertação completa (PDF, 1.5 MB)
Apresentação da defesa (PDF, 1.1 MB)
Leia a introdução da dissertação em markdown

Referências

Orientador: Prof. Dr. José Coelho de Pina Jr. (IME-USP)
Área: Ciência da Computação — Origami Computacional
Ano: 2005–2007
Código-fonte: JOrigami no SourceForge