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 ₁ , x ₂ ) ∈ R ² | x²
₁+ x²
₂+ sin( x ₁ + x ₂ ) ∈ [4,9]}
con diferentes precisiones. El conjunto X⁻ corresponde a las cajas rojas y el conjunto X⁺ contiene todas las cajas rojas y amarillas.

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

^ 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.
^ 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.
^ 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).
^ 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.
^ Jaulin, L. (2001). "Planificación de rutas utilizando intervalos y gráficos" (PDF) . Computación confiable . 7 (1).
^ 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.

[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.