stringtranslate.com

Subpavimentación

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

En R¹ las cajas son segmentos de recta, en R² rectángulos y en Rⁿ hiperrectángulos. Un subpavimento R² puede ser también un " teselado irregular por rectángulos", cuando no tiene huecos.

Corchetes del conjunto rayado X entre dos subpavimentos. Cuadros rojos: subpavimento interior. Rojo y amarillo: subpavimento exterior. La diferencia , exterior menos interior, es una aproximación del límite .

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

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

Ejemplo

Las tres figuras de la derecha a continuación 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 las cajas rojas y el conjunto X⁺ contiene todas las cajas rojas y amarillas.

Subpavimentos que enmarcan un conjunto con una resolución baja
Subpavimentos que enmarcan el mismo conjunto con una resolución moderada
Subpavimentos que enmarcan el conjunto con una alta resolución

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

Referencias

  1. ^ Kieffer, M.; Braems, I.; Walter, É.; Jaulin, L. (2001). "Cálculo 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. ^ Jaulin, Luc; Walter, Eric (1993). "Inversión de conjuntos mediante análisis de intervalos para estimación no lineal de error acotado" (PDF) . Automatica . 29 (4): 1053–1064. doi :10.1016/0005-1098(93)90106-4.
  3. ^ Delanoue, N.; Jaulin, L.; Cotenceau, B. (2005). "Uso de la aritmética de intervalos para demostrar que un conjunto está conexo por trayectorias" (PDF) . Theoretical Computer Science . 351 (1).
  4. ^ Delanoue, N.; Jaulin, 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 clase en informática. Vol. 3732. págs. 93–101. doi :10.1007/11558958_11. ISBN 978-3-540-29067-4.
  5. ^ Jaulin, L. (2001). "Planificación de rutas utilizando intervalos y gráficos" (PDF) . Computación confiable . 7 (1).
  6. ^ Kieffer, M.; Jaulin, L.; Braems, I.; Walter, E. (2001). "Computación 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.