stringtranslate.com

Subpavimento

En matemáticas , un subpavimento es un conjunto de cajas de R⁺ que no se superponen . Un subconjunto X de Rⁿ puede aproximarse mediante dos subpavimentos X⁻ y X⁺ tales que
 X⁻  ⊂  X  ⊂  X⁺ .

En R¹ los cuadros son segmentos de línea, en R² rectángulos y en Rⁿ hiperrectángulos. Un subpavimento R² puede ser también un " alicatado irregular por rectángulos", cuando no tiene huecos.

Horquillado del conjunto sombreado X entre dos subpavimentos. Cuadros rojos: subpavimento interior. Rojo y amarillo: subpavimento exterior. La diferencia , exterior menos interior, es una aproximación de límites .

Las cajas presentan la ventaja de ser muy fácilmente manipuladas por las computadoras, ya que forman el corazón del análisis de intervalos . Muchos algoritmos de intervalo proporcionan naturalmente soluciones que son subpavimentos regulares. [1]

En informática , una aplicación bien conocida del subpavimento en R² es la estructura de datos Quadtree . En el contexto del rastreo de imágenes y otras aplicaciones, es importante ver X⁻ como un interior topológico , como se ilustra.

Ejemplo

Las tres figuras de la derecha muestran una aproximación del conjunto
  X = {( x 1 , x 2 ) ∈  R 2 | X2
1+ x2
2+ sin( x 1  +  x 2 ) ∈ [4,9]}
con diferentes precisiones. El conjunto X⁻ corresponde a cuadros rojos y el conjunto X⁺ contiene todos los cuadros rojos y amarillos.

Subpavimentos que delimitan un conjunto de baja resolución
Subpavimentos que agrupan el mismo conjunto con una resolución moderada
Subpavimentos que delimitan el conjunto con alta resolución

Combinados con métodos basados ​​en intervalos , los subpavimentos se utilizan para aproximar el conjunto de soluciones de problemas no lineales, como los problemas de inversión de conjuntos . [2] Los subpavimentos también se pueden utilizar para demostrar que un conjunto definido por desigualdades no lineales está conectado por caminos , [3] para proporcionar propiedades topológicas de dichos conjuntos, [4] para resolver problemas de piano-mover [5] o para implementar el cálculo de conjuntos. [6]

Referencias

  1. ^ Kieffer, M.; Braems, I.; Walter, É.; Jaulín, L. (2001). "Cómputo de conjuntos garantizados con subpavimentos" (PDF) . Computación científica, números validados, métodos de intervalo . págs. 167-172. doi :10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8.
  2. ^ Jaulín, Luc; Walter, Eric (1993). "Establecer inversión mediante análisis de intervalos para estimación de error acotado no lineal" (PDF) . Automática . 29 (4): 1053–1064. doi :10.1016/0005-1098(93)90106-4.
  3. ^ Delanoue, N.; Jaulín, L.; Cotenceau, B. (2005). "Uso de la aritmética de intervalos para demostrar que un conjunto está conexo por caminos" (PDF) . Informática Teórica . 351 (1).
  4. ^ Delanoue, N.; Jaulín, L.; Cotenceau, B. (2006). "Conteo del número de componentes conectados de un conjunto y su aplicación a la robótica" (PDF) . Computación Paralela Aplicada. Estado del Arte en Computación Científica . Apuntes de conferencias sobre informática. vol. 3732, págs. 93-101. doi :10.1007/11558958_11. ISBN 978-3-540-29067-4.
  5. ^ Jaulín, L. (2001). "Planificación de rutas mediante intervalos y gráficos" (PDF) . Computación confiable . 7 (1).
  6. ^ Kieffer, M.; Jaulín, L.; Braems, I.; Walter, E. (2001). "Cómputo de conjuntos garantizados con subpavimentos" (PDF) . Computación científica, números validados, métodos de intervalo . En W. Kraemer y JW Gudenberg (Eds), Computación científica, números validados, métodos de intervalo, Kluwer Academic Publishers. págs. 167-178. doi :10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8.