Pavage d'un polygone rectilinéaire avec des carrés

Session : PPP-4 / Placement, Partionnement, Packing
Vendredi 12 février 10:30 - 11:50 Salle : CI2-22
Mirsad Buljubasic et Michel Vasquez

Dans cet article nous présentons une approche heuristique pour traiter le problème de partition d'un polygone rectilinéaire par des carrés. Ce problème a été posé à la communauté scientifique par la société COMPRESS-VISTAPRINT en mai 2015. Contrairement au cas de la partition en un nombre minimum de rectangles on ne connait pas, aujourd'hui, d'algorithme polynomial pour la partition par des carrés. Notre algorithme de résolution approximative combine la programmation linéaire avec des procédures gloutonnes. Il a été classé parmi les 10 meilleurs lors de la compétition organisée par CIMPRESS-VISTAPRINT à laquelle ont participé plus de 600 équipes.

Mots clés : partition, programmation linéaire, algorithme glouton