Rectángulo vacío más grande

En geometría computacional , el problema del rectángulo vacío más grande, ^[2] problema del rectángulo vacío máximo ^[3] o problema del rectángulo vacío máximo , ^[4] es el problema de encontrar un rectángulo de tamaño máximo para colocarlo entre obstáculos en el plano. Existen varias variantes del problema, dependiendo de las particularidades de esta formulación genérica, en particular, dependiendo de la medida del "tamaño", del dominio (tipo de obstáculos) y de 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 del diseño físico 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 linda 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 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.

Clasificación

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 por ejes o orientados arbitrariamente.

Casos especiales

Cuadrado de área máxima

El caso en el que el rectángulo buscado es un cuadrado orientado a un eje se puede tratar utilizando 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] ${\ Displaystyle L_ {1}}$ $\Theta (n\log n)$

Dominio: rectángulo que contiene puntos

Un problema discutido por primera vez por Naamad, Lee y Hsu en 1983 ^[1] se plantea de la siguiente manera: dado un rectángulo A que contiene n puntos, encuentre un rectángulo de área más grande con lados paralelos a los de A que se encuentre dentro de A y que no contenga ningún de los puntos dados. Naamad, Lee y Hsu presentaron un algoritmo de complejidad temporal , donde s es el número de soluciones factibles, es decir, rectángulos vacíos máximos. También demostraron eso y dieron un ejemplo en el que s es cuadrático en n . Posteriormente, varios artículos presentaron mejores algoritmos para el problema. $O(\min(n^{2},s\log n))$ $s=O(n^{2})$

Dominio: obstáculos del segmento de línea

El problema de los rectángulos isotéticos vacíos entre segmentos de recta isotéticos se consideró por primera vez ^[9] en 1990. ^[10] Posteriormente se consideró un problema más general de rectángulos isotéticos vacíos entre obstáculos no isotéticos. ^[9]

Generalizaciones

Dimensiones superiores

En el espacio tridimensional, los algoritmos son conocidos por encontrar el problema de cuboide isotético vacío máximo más grande , así como por la enumeración de todos los cuboides vacíos isotéticos máximos. ^[11]

Ver también

Referencias

^ ab A. Naamad, DT Lee y W.-L. Hsu (1984). "Sobre el problema del rectángulo vacío máximo". Matemática Aplicada Discreta . 8 (3): 267–277. doi : 10.1016/0166-218X(84)90124-0 .
^ "Busque en Google Scholar el uso del término" rectángulo vacío más grande ".
^ "Busque en Google Scholar el uso del término" rectángulo vacío máximo ".
^ "Busque en Google Scholar el uso del término" rectángulo vacío máximo ".
^ Jeffrey Ullman (1984). "Capítulo 9: Algoritmos para herramientas de diseño VLSI". Aspectos computacionales de VLSI . Prensa de Ciencias de la Computación. ISBN 0-914894-95-1.Describe algoritmos para operaciones poligonales involucradas en la automatización del diseño electrónico ( verificación de reglas de diseño , extracción , ubicación y enrutamiento de circuitos ).
^ Baird, HS, Jones, SE, Fortune, SJ (1990). "Segmentación de imágenes mediante portadas dirigidas por formas". [1990] Actas. Décimo Congreso Internacional sobre Reconocimiento de Patrones . vol. 1. págs. 820–825. doi :10.1109/ICPR.1990.118223. ISBN 0-8186-2062-5. S2CID 62735730.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
^ Alok Aggearwal, Subhash Suri (1987). "Algoritmos rápidos para calcular el rectángulo vacío más grande". Actas del tercer simposio anual sobre geometría computacional - SCG '87 . págs. 278–290. doi :10.1145/41958.41988. ISBN 0897912314. S2CID 18500442.
^ B. Chazelle , RL Drysdale III y DT Lee (1984). "Calcular el rectángulo vacío más grande". STACS-1984, Apuntes de conferencias sobre informática . Apuntes de conferencias sobre informática. 166 : 43–54. doi :10.1007/3-540-12920-0_4. ISBN 978-3-540-12920-2.
^ ab Thiagarajan, PS (23 de noviembre de 1994). "Ubicación del rectángulo vacío más grande entre obstáculos arbitrarios". Fundamentos de la tecnología del software y la informática teórica . Saltador. pag. 159.ISBN 9783540587156.
^ Subhas C Nandy; Bhargab B Bhattacharya; Rayo Sibabrata (1990). "Algoritmos eficientes para identificar todos los rectángulos vacíos isotéticos máximos en el diseño de diseño VLSI". Proc. FST y TCS - 10, Apuntes de conferencias sobre informática . Apuntes de conferencias sobre informática. 437 : 255–269. doi :10.1007/3-540-53487-3_50. ISBN 978-3-540-53487-7.
^ SC Nandy; BB Bhattacharya (1998). "Cubosides vacíos máximos entre puntos y bloques". Computadoras y Matemáticas con Aplicaciones . 36 (3): 11-20. doi : 10.1016/S0898-1221(98)00125-4 .