서브페이빙

Subpaving

수학에서 서브페이빙은 R'의 겹치지 않는 상자 세트입니다.R'의 서브셋X는 다음과 같이 2개의 서브구간 X'와 X'로 근사할 수 있다.
X' X' X' X'

R'에서 상자는 선분, R² 직사각형 및 R' 하이퍼직각형의 경우입니다.R² 하위 포장은 구멍이 없는 경우 "사각형에 의한 비정규 타일링"이 될 수도 있습니다.

2개의 서브패킹 사이에 있는 부화 세트 X의 브래킷.빨간색 상자: 내부 서브포장.빨간색 및 노란색: 외부 서브포장.외측에서 내측을 뺀 차이는 경계 근사치입니다.

박스는 인터벌 분석의 핵심을 형성하기 때문에 컴퓨터에 의해 매우 쉽게 조작될 수 있다는 장점을 제시합니다.많은 인터벌알고리즘은 통상적인 [1]서브페이징인 솔루션을 제공합니다.

계산에서 R²에서의 서브페이핑의 잘 알려진 적용은 쿼드트리 데이터 구조입니다.이미지 트레이스 컨텍스트 및 기타 어플리케이션에서는 그림과 같이 X'를 토폴로지 내부로 보는 것이 중요합니다.

예

아래 오른쪽에 있는 세 그림은 세트의 근사치를 보여 줍니다.
X = {(x1, x2) rx22
1 Rx + x2
2 + sin(x1 + x2) [ [4,9]}
다른 정확도로요.세트 X'는 빨간색 상자에 대응하고 세트 X'에는 빨간색 및 노란색 상자가 모두 포함됩니다.

낮은 분해능으로 세트를 브래킷으로 묶는 하위 포장
같은 세트를 중간 해상도로 괄호하는 서브패닝
고해상도로 세트를 브래킷으로 묶는 하위 포장

구간 기반 방법과 조합하여 서브페이빙을 사용하여 설정된 반전 [2]문제와 같은 비선형 문제의 솔루션 세트를 근사합니다.또한, 서브파빙은 비선형 부등식에 의해 정의된 집합이 경로로 연결되어 [3]있다는 것을 증명하고, [4]그러한 집합의 위상 특성을 제공하며, 피아노 무버의[5] 문제를 해결하거나 집합 [6]계산을 구현하기 위해 사용될 수 있다.

레퍼런스

  1. ^ Kieffer, M.; Braems, I.; Walter, É.; Jaulin, L. (2001). "Guaranteed Set Computation with Subpavings". Scientific Computing, Validated Numerics, Interval Methods: 167–172. doi:10.1007/978-1-4757-6484-0_14.
  2. ^ Jaulin, Luc; Walter, Eric (1993). "Set inversion via interval analysis for nonlinear bounded-error estimation" (PDF). Automatica. 29 (4): 1053–1064. doi:10.1016/0005-1098(93)90106-4.
  3. ^ Delanoue, N.; Jaulin, L.; Cottenceau, B. (2005). "Using interval arithmetic to prove that a set is path-connected" (PDF). Theoretical Computer Science. 351 (1).
  4. ^ Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). "Counting the Number of Connected Components of a Set and Its Application to Robotics" (PDF). Applied Parallel Computing, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 3732 (1): 93–101. doi:10.1007/11558958_11. ISBN 978-3-540-29067-4.
  5. ^ Jaulin, L. (2001). "Path planning using intervals and graphs" (PDF). Reliable Computing. 7 (1).
  6. ^ Kieffer, M.; Jaulin, L.; Braems, I.; Walter, E. (2001). "Guaranteed set computation with subpavings" (PDF). In W. Kraemer and J. W. Gudenberg (Eds), Scientific Computing, Validated Numerics, Interval Methods, Kluwer Academic Publishers: 167–178. doi:10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8.