Hispanopedia Wiki
Articulo de referencia

Rectángulo vacío más grande

Rectángulos vacíos máximos (en verde) con diferentes objetos delimitadores (con contorno negro). El rectángulo verde claro sería una solución subóptima (no máxima). AC están ori...

Hispanopedia WikiContenido en espanolLectura gratuita
Rectángulos vacíos máximos (en verde) con diferentes objetos delimitadores (con contorno negro). El rectángulo verde claro sería una solución subóptima (no máxima). AC están orientados a los ejes, paralelos a los ejes del "suelo" azul claro y también ejemplos de. [ 1 ] E muestra un rectángulo vacío máximo con orientación arbitraria

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", 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 los 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 limita 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 segmentación de imágenes, I+D de procesamiento de imágenes y reconocimiento de patrones . [ 6 ] En el contexto 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 demuestra 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 consiste en determinar si el rectángulo se busca entre rectángulos orientados según un eje o entre rectángulos orientados arbitrariamente.

Casos especiales

Cuadrado de área máxima

El caso en que el rectángulo buscado es un cuadrado orientado por un eje puede tratarse utilizando diagramas de Voronoi enL1{\displaystyle L_{1}}métricas para el conjunto de obstáculos correspondiente, de forma similar al problema del círculo vacío más grande . En particular, para el caso de puntos dentro de un rectángulo, un algoritmo óptimo de complejidad temporal.Θ(norteregistro⁡norte){\displaystyle \Theta (n\log n)}es conocido. [ 8 ]

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, encontrar un rectángulo de área máxima con lados paralelos a los de A que se encuentre dentro de A y no contenga ninguno de los puntos dados. Naamad, Lee y Hsu presentaron un algoritmo de complejidad temporalO(min(norte2,sregistro⁡norte)){\displaystyle O(\min(n^{2},s\log n))}donde s es el número de soluciones factibles, es decir, rectángulos vacíos máximos. También demostraron ques=O(norte2){\displaystyle s=O(n^{2})}y dio un ejemplo en el que s es cuadrática en n . Posteriormente, varios artículos presentaron mejores algoritmos para el problema.

Dominio: obstáculos de segmentos de línea

El problema de los rectángulos isotéticos vacíos entre segmentos de línea 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, se conocen algoritmos para encontrar el cuboide isotético vacío máximo más grande , así como para enumerar todos los cuboides isotéticos vacíos máximos. [ 11 ]

Véase también

Referencias

  1. 1 2 A. Naamad, DT Lee y W.-L. Hsu (1984). "Sobre el problema del rectángulo vacío máximo" . Matemáticas aplicadas discretas . 8 (3): 267– 277. doi : 10.1016/0166-218X(84)90124-0 .
  2. ↑ "Busca en Google Académico el uso del término "rectángulo vacío más grande"" .
  3. ↑ "Busca en Google Académico el uso del término "rectángulo vacío máximo"" .
  4. ↑ "Busca en Google Académico el uso del término "rectángulo vacío máximo"" .
  5. ↑ Jeffrey Ullman (1984). "Cap. 9: Algoritmos para herramientas de diseño VLSI". Aspectos computacionales de VLSI . Computer Science Press. 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 de circuitos , colocación y enrutamiento ).
  6. ↑ Baird, HS, Jones, SE, Fortune, SJ (1990). "Segmentación de imágenes mediante cubiertas dirigidas por forma". [ 1990 ] Actas. 10.ª Conferencia Internacional sobre Reconocimiento de Patrones . Vol. 1. pp. 820–825 . doi : 10.1109/ICPR.1990.118223 . ISBN   0-8186-2062-5. S2CID 62735730 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  7. ↑ 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 . 
  8. ↑ B. Chazelle , RL Drysdale III y DT Lee (1984). "Cálculo del rectángulo vacío más grande". STACS-1984, Lecture Notes in Computer Science . Lecture Notes in Computer Science. 166 : 43–54 . doi : 10.1007/3-540-12920-0_4 . ISBN 978-3-540-12920-2.
  9. 1 2 Thiagarajan, PS (23 de noviembre de 1994). "Localizació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 . Springer. pág. 159. ISBN  9783540587156.
  10. ↑ Subhas C Nandy; Bhargab B Bhattacharya; Sibabrata Ray (1990). "Algoritmos eficientes para identificar todos los rectángulos vacíos isotéticos máximos en el diseño de circuitos integrados VLSI". Proc. FST & TCS – 10, Lecture Notes in Computer Science . Lecture Notes in Computer Science. 437 : 255–269 . doi : 10.1007/3-540-53487-3_50 . ISBN 978-3-540-53487-7.
  11. ↑ SC Nandy; BB Bhattacharya (1998). "Cuboides vacíos máximos entre puntos y bloques" . Computers & Mathematics with Applications . 36 (3): 11– 20. doi : 10.1016/S0898-1221(98)00125-4 .