Le plus grand rectangle vide

En géométrie computationnelle , le problème du plus grand rectangle vide, problème du rectangle vide maximal ou problème du rectangle vide maximal , est le problème de trouver un rectangle de taille maximale à placer parmi les obstacles dans le plan. Il existe un certain nombre de variantes du problème, en fonction des particularités de cette formulation générique, en particulier, en fonction de la mesure de la « taille », du domaine (type d'obstacles) et de l'orientation du rectangle.

Les problèmes de ce type se posent par exemple dans l'automatisation de la conception électronique , dans la conception et la vérification de la disposition physique des circuits intégrés .

Un rectangle vide maximal est un rectangle qui n'est pas contenu dans un autre rectangle vide. Chaque côté d'un rectangle vide maximal est contigu à un obstacle (sinon le côté peut être décalé vers l'extérieur, augmentant le rectangle vide). Une application de ce type est l'énumération des « rectangles blancs maximaux » dans la R&D de segmentation d'images pour le traitement d'images et la reconnaissance de formes . Dans le contexte de nombreux algorithmes pour les plus grands rectangles vides, les « rectangles vides maximaux » sont des solutions candidates à prendre en compte par l'algorithme, car il est facilement prouvé que, par exemple, un rectangle vide de surface maximale est un rectangle vide maximal.

En termes de mesure de taille, les deux cas les plus courants sont le rectangle vide de plus grande surface et le rectangle vide de plus grand périmètre.

Une autre classification importante est de savoir si le rectangle est recherché parmi les rectangles orientés selon un axe ou orientés arbitrairement.

Le cas où le rectangle recherché est un carré orienté selon un axe peut être traité à l'aide de diagrammes de Voronoi en métrique pour l'ensemble d'obstacles correspondant, de manière similaire au problème du plus grand cercle vide . En particulier, pour le cas de points dans un rectangle, un algorithme optimal de complexité temporelle est connu.

Un problème discuté pour la première fois par Naamad, Lee et Hsu en 1983 est énoncé comme suit : étant donné un rectangle A contenant n points, trouver un rectangle de plus grande aire avec des côtés parallèles à ceux de A qui se trouve dans A et ne contient aucun des points donnés. Naamad, Lee et Hsu ont présenté un algorithme de complexité temporelle , où s est le nombre de solutions réalisables, c'est-à-dire le nombre maximal de rectangles vides. Ils ont également prouvé cela et ont donné un exemple dans lequel s est quadratique en n . Par la suite, un certain nombre d'articles ont présenté de meilleurs algorithmes pour le problème.

Le problème des rectangles isothétiques vides parmi des segments de ligne isothétiques a été considéré pour la première fois en 1990. Plus tard, un problème plus général de rectangles isothétiques vides parmi des obstacles non isothétiques a été considéré.

Dans l'espace tridimensionnel, des algorithmes sont connus pour trouver le plus grand problème de cuboïde isothétique vide maximal , ainsi que pour l'énumération de tous les cuboïdes isothétiques vides maximaux.