Rectángulo vacío más grande
En geometría computacional , el problema de rectángulo vacío más grande, [2] problema de rectángulo vacío máximo [3] o problema de rectángulo vacío máximo , [4] es el problema de encontrar un rectángulo de tamaño máximo para colocar entre obstáculos en el plano. Hay una serie de variantes del problema, según las particularidades de esta formulación genérica, en particular, según la medida del "tamaño", el dominio (tipo de obstáculos) y la orientación del rectángulo.
Los problemas de este tipo surgen, por ejemplo, en la automatización del diseño electrónico , en el diseño y verificación de la disposición física de circuitos integrados . [5]
Un rectángulo vacío máximo es un rectángulo que no está contenido en otro rectángulo vacío. Cada lado de un rectángulo vacío máximo colinda con un obstáculo (de lo contrario, el lado puede desplazarse hacia afuera, aumentando el rectángulo vacío). Una aplicación de este tipo es la enumeración de "rectángulos blancos máximos" en la I + D de segmentación de imágenes de procesamiento de imágenes y reconocimiento de patrones . [6] En los contextos de muchos algoritmos para los rectángulos vacíos más grandes, los "rectángulos vacíos máximos" son soluciones candidatas a ser consideradas por el algoritmo, ya que se prueba fácilmente que, por ejemplo, un rectángulo vacío de área máxima es un rectángulo vacío máximo.
En términos de medida de tamaño, los dos casos más comunes son el rectángulo vacío de mayor área y el rectángulo vacío de mayor perímetro. [7]
Otra clasificación importante es si el rectángulo se busca entre rectángulos orientados al eje u orientados arbitrariamente.
El caso en el que el rectángulo buscado es un cuadrado orientado al eje puede tratarse usando diagramas de Voronoi en métricas para el conjunto de obstáculos correspondiente, de manera similar al problema del círculo vacío más grande . En particular, para el caso de puntos dentro de un rectángulo, se conoce un algoritmo óptimo de complejidad temporal . [8]
