Comment trouver le rectangle de surface maximale à l'intérieur d'un polygone convexe?

Dans cet article, nous recherchons des algorithmes / idées sur la façon de trouver le rectangle de zone maximale à l' intérieur d'un polygone convexe .

Dans la figure suivante, les nombres sont les zones des rectangles ajustés. Comme indiqué, un rectangle souhaité peut varier dans chaque dimension et peut être dans n'importe quel angle.

Éditer:

Nous n'avons aucune idée claire de la façon de traiter le problème mentionné, comme nous l'avons demandé ici. Néanmoins, nous supposons que le rectangle d'aire maximale peut être l'un de ceux qui ont un bord aligné sur (pas nécessairement le même bord de longueur, bien sûr) un bord du polygone.

Quelques notes trop grosses pour être insérées dans un commentaire (bien que cela ne suggère pas un algorithme évident):

La ligne de poinçonnage (MODIFIEE) : au moins deux sommets du rectangle d'aire maximale doivent se trouver à la limite du polygone (c.-à-d. Le long d'une arête ou à un sommet). Et si le rectangle d'aire maximale n'est pas un carré, alors au moins trois sommets doivent se trouver à la limite du polygone.

Je l'ai prouvé en quatre étapes:

Remarque n ° 1 : au moins un sommet du rectangle d'aire maximale se trouvera toujours à la limite du polygone. C'est assez évident, mais une preuve pourrait ressembler à ceci (par contradiction): Supposons que vous ayez un rectangle "maximal" sans sommet à la frontière du polygone. Cela signifie qu'il y aurait au moins une petite pièce autour de chacun de ses sommets. Vous pouvez donc agrandir un peu votre rectangle, contredisant sa maximalité.

Remarque n ° 2 : au moins deux sommets du rectangle de la surface maximale se trouveront toujours à la limite du polygone. Une preuve pourrait ressembler à ceci (encore une fois par contradiction): Supposons que vous ayez un rectangle "maximal" avec un seul sommet sur la frontière (garanti par la note # 1). Considérez les deux arêtes non adjacentes à ce sommet. Étant donné que leurs points d'extrémité ne sont PAS sur la frontière, il y a une petite place autour de chacun. Ainsi, l'un ou l'autre de ces bords pourrait être "extrudé" un peu, élargissant la zone du polygone et contredisant sa maximalité.

Remarque # 3 : Il y a deux sommets diagonalement opposés du rectangle d'aire maximale qui se trouvent à la limite du polygone. (Nous savons par la note n ° 2 qu'il y en a au moins deux, mais pas nécessairement qu'ils sont en face l'un de l'autre.) sont à la limite) pourrait être extrudé un peu, augmentant la surface du rectangle et contredisant sa maximalité.

Remarque n ° 4 : (MODIFIÉ) Si le rectangle de la zone maximale n'est pas un carré, alors trois de ses sommets se trouveront à la limite du polygone.

Pour prouver, supposons que ce n'est pas le cas, c'est-à-dire que le rectangle d'aire maximale n'est pas un carré, mais seulement deux de ses sommets se trouvent à la frontière du polygone. Je vais montrer comment construire un rectangle plus grand, contredisant la maximalité.

Appelez les sommets du rectangle A, B, Cet D. Sans perte de généralité, supposez cela Bet ce Dsont les deux qui se trouvent sur la frontière du polygone. Depuis Aet Cà l'intérieur du polygone, il y a une certaine marge de manœuvre autour d'eux (représentés par des cercles autour Aet Cdans l'image ci-dessous). Maintenant, dessinez un cercle autour du rectangle et faites glisser les points Aet Cun peu autour du cercle de la même quantité (pour faire A'et C', illustré ci-dessous) de sorte que le nouveau rectangleA'BC'Dest plus carré que le rectangle d'origine. Ce processus crée un nouveau rectangle qui se trouve également dans le polygone d'origine et a une plus grande surface. C'est une contradiction, donc la preuve est faite.

Pour croire cette preuve, vous devez vous convaincre que l'aire d'un rectangle inscrit dans un cercle augmente à mesure qu'il devient "plus carré" (c'est-à-dire que la différence entre les longueurs de bord diminue). Vous devez également que le polygone soit convexe pour que les nouvelles lignes soient toutes à l'intérieur. Et il y a probablement d'autres petits détails sous le tapis, mais je suis presque sûr qu'ils fonctionnent tous.

J'ai fait un croquis très rapide et hideux sur votre note verte dans la question. Je ne pouvais pas le poster comme commentaire, j'ai donc dû écrire une réponse, même si ce n'est pas le cas.
Je crois que dans l'image ci-dessous, nous avons un rectangle de zone maximale (pas parfait, c'est juste un croquis fait sur Paint pour donner une idée), et je ne pense pas que vous puissiez en trouver un plus grand qui aurait un côté commun avec le bordures du plygon noir ...
Cependant je peux me tromper, dans ce cas vous avez toutes mes excuses.

La plupart des autres algorithmes trouvent la surface maximale rectangle rectiligne inscrit dans un polygone convexe et ont une complexité de O(log n). Je ne pense pas que votre supposition que le polygone de la zone maximale soit aligné avec l'un des côtés soit correcte, car tout ce que vous auriez à faire serait de faire pivoter les ntemps du polygone , ce qui entraînerait une complexité O(n log n)et, dans ma brève recherche, je ne pourrais pas trouver quoi que ce soit disant que c'était aussi simple que cela.

Cependant, l'article Les plus grands rectangles inscrits dans les polygones convexes de Knauer, et. al., décrit un algorithme d'approximation qui vous rapprochera de la bonne réponse.

D'après ce que je comprends de l'algorithme, il s'appuie sur l'un des polygones connus de la zone maximale alignée sur l'axe, puis échantillonne au hasard les points à l'intérieur de l'espace de polyon, génère plusieurs axes à partir de ces échantillons aléatoires, itère sur cet axe et applique l'axe -algorithme aligné à chacun, puis renvoie le plus grand rectangle de cet ensemble.