Décomposition équidécomposable minimale

10

Étant donné deux polyèdres et Q , P et Q sont équidécomposables s'il existe des ensembles finis de polyèdres P 1 , , P n et Q 1 , , Q n tels que P i et Q i sont congruents pour tout i , P = n i = 1 P i et Q = n i = 1 QPQPQP1,,PnQ1,,QnPiQiiP=i=1nPi . On saitque si P et Q sont des polygones de surface égale, une tellecomposition équidiqueexiste toujours et que celanevautgénéralement pas pour les dimensions supérieures. Q=i=1nQiPQ

Je suis curieux de connaître la complexité du problème d'équidécomposition minimale:

Pour deux polygones et Q , trouver une équidécomposition P 1 , , P n et Q 1 , , Q n qui minimise n .PQP1,,PnQ1,,Qnn

Existe-t-il des algorithmes (exacts, polynomiaux, exponentiels, approximatifs) pour cela? La complexité est-elle connue?

Glencora Borradaile
la source
2
bienvenue, super blog !
vzn

Réponses:

6

Pour les régions unidimensionnelles déconnectées avec des coordonnées entières, la composition équidécimale en un nombre minimum de pièces est fortement NP-difficile via une réduction facile à 3SUM: si une forme a des segments dont les longueurs sont les entrées 3SUM et l'autre a des segments dont les longueurs sont les cases vous devez les emballer, puis vous pouvez le faire sans découpe supplémentaire si l'instance 3SUM est résoluble. Pour les polygones bidimensionnels, cela reste difficile, même pour les régions connectées: épaississez les segments d'un problème unidimensionnel en rectangles de hauteur unitaire et connectez-les par de minces "chaînes" qui ont une zone trop petite pour affecter la partie 3SUM du problème mais sont faciles à manipuler dans la décomposition.

(Avertissement: j'ai emprunté cette idée de réduction à un travail conjoint non encore publié avec de nombreuses autres personnes sur la dureté de certains autres problèmes.)

David Eppstein
la source
Votre avertissement semble être en fait une reconnaissance! :-)
David Richerby