Partitionner un rectangle sans endommager les rectangles intérieurs

12

C est un rectangle à axe parallèle.

C1,,Cn sont des rectangles parallèles axe-parallèle disjoints tels que , comme ceci:C1CnC

entrez la description de l'image ici

Une partition préservant le rectangle de C est une partition C=E1EN , de telle sorte que Nn , les Ei sont des rectangles parallèles à axes parallèles disjoints, et pour chaque i=1,,n : CiEi , c'est-à-dire que chaque rectangle existant est contenu dans un nouveau rectangle unique, comme ceci:

entrez la description de l'image ici

Qu'est-ce qu'un algorithme pour trouver une partition préservant le rectangle avec un petit ?N

En particulier, existe-t-il un algorithme pour trouver une partition préservant le rectangle avec parties?N=O(n)

Erel Segal-Halevi
la source

Réponses:

4

NOUVELLE RÉPONSE: l'algorithme simple suivant est asymptotiquement optimal:

arbitrairement chacun des rectangles , dans toute la mesure du possible, de telle sorte que les rectangles restent disjoints deux à deux.Ci

Le nombre de trous est au maximum de . Ceci est asymptotiquement optimal, car il existe des configurations dans lesquelles le nombre de trous est d'au moins .k2kO(k)

Les preuves sont dans cet article .


ANCIENNE RÉPONSE:

L'algorithme suivant, bien qu'il ne soit pas optimal, est apparemment suffisant pour trouver une partition préservant le rectangle avec parties.N=O(n)

L'algorithme fonctionne avec un polygone rectiligne , qui est initialisé au rectangle .PC

Phase 1: Choisissez un rectangle qui est adjacent à une limite ouest de (c'est-à-dire qu'il n'y a pas d'autre rectangle entre le côté ouest de et une limite ouest de ). La place dans et l' étirer jusqu'à ce qu'il touche la limite ouest de . Soit (pour ) la version étirée de . Soit . Répéter la phase 1 fois jusqu'à ce que tous lesCiPCjCiPCiPPEii=1,,nCiP=PEinndes rectangles originaux sont placés et étirés. Dans l'image ci-dessous, un ordre possible de placement des rectangles est :C1,C2,C4,C3

entrez la description de l'image ici

Maintenant, est un polygone rectiligne (éventuellement déconnecté), comme ceci:P

entrez la description de l'image ici

Je prétends que le nombre de sommets concaves dans est au plus . En effet, chaque fois qu'un rectangle étiré est supprimé de , il y a 3 possibilités:P2nP

  • 2 nouveaux sommets concaves sont ajoutés (comme lors du placement de );C1,C4
  • 3 nouveaux sommets concaves sont ajoutés et 1 est supprimé (comme avec );C3
  • 4 nouveaux sommets concaves sont ajoutés et 2 sont supprimés (comme avec ).C2

Phase 2: Partition en rectangles parallèles à l'axe en utilisant un algorithme existant (voir Keil 2000, pages 10-13 et Eppstein 2009, pages 3-5 pour une revue).P

Keil cite un théorème qui dit que le nombre de rectangles dans une partition minimale est limité par 1 + le nombre de sommets concaves. Par conséquent, dans notre cas, le nombre est au plus , et le nombre total de rectangles dans la partition est .2n+1N3n+1


Cet algorithme n'est pas optimal. Par exemple, dans l'exemple ci-dessus, cela donne tandis que la solution optimale a . Il reste donc deux questions:N=13N=5

A. Cet algorithme est-il correct?

B. Existe-t-il un algorithme polynomial pour trouver le optimal , ou au moins une meilleure approximation?N

Erel Segal-Halevi
la source
Eh bien, dans la phase 1, vous ajoutez des cellules de partition, chacune contenant exactement un rectangle initial et ne se chevauchant pas sur un autre. Dans la phase 2, vous partitionnez l'espace restant, de sorte que les cellules créées dans la phase 2 n'entrecoupent aucun rectangle initial. La preuve de la correction semble plutôt simple, ou ai-je raté quelque chose?
Boson
@Boson le point sur lequel je ne suis pas sûr est que le nombre de sommets concaves est au maximum de . Il semble "évident" qu'il n'y a que 3 possibilités comme je l'ai écrit, mais j'ai peut-être manqué une autre possibilité. 2n
Erel Segal-Halevi