サブペイビング

幾何学的物体

数学において、部分舗装とはR⁺の重なり合わない箱の集合である。Rⁿの部分集合X は、X⁻ ⊂ X ⊂ X⁺を満たす2つの部分舗装X⁻とX⁺で近似できる。

R¹ではボックスは線分であり、R²では長方形、Rⁿでは超長方形です。R²の部分舗装は、穴がない場合、「長方形による非正規なタイリング」とも言えます。

2つのサブ舗装の間にあるハッチングされた集合Xを囲む。赤い枠：内側のサブ舗装。赤と黄色の枠：外側のサブ舗装。外側のサブ舗装から内側のサブ舗装を引いた差が境界近似値である。

ボックスは区間解析の中核を成すため、コンピュータによる操作が非常に容易であるという利点がある。多くの区間アルゴリズムは、自然に正規の部分舗装となる解を提供する。^[1]

計算分野において、 R²における部分舗装のよく知られた応用として四分木データ構造が挙げられます。画像トレースなどの応用においては、図に示すように、 X⁻を位相的な内部構造として捉えることが重要です。

例

下の右側の3つの図は、集合
X = {( x ₁ , x ₂ ) ∈ R ² | xの近似を示しています²
₁+ ×²
₂+ sin( x ₁ + x ₂ ) ∈ [4,9]} の2
つの関数を異なる精度で組み合わせて計算する。集合X⁻は赤いボックスに対応し、集合X⁺はすべての赤と黄色のボックスを含む。

区間ベースの方法と組み合わせて、サブペイビングは集合反転問題などの非線形問題の解集合を近似するために使用されます。^{[2]サブペイビングは、非線形}不等式によって定義された集合がパス接続されていることを証明したり、^{[3]そのような集合の}位相特性を提供したり、^[4]ピアノムーバー問題^[5]を解決したり、集合計算を実装したりするためにも使用できます。^[6]

参考文献

^ Kieffer, M.; Braems, I.; Walter, É.; Jaulin, L. (2001). 「部分舗装による保証集合計算」(PDF) . Scientific Computing, Validated Numerics, Interval Methods . pp. 167– 172. doi :10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8。
^ Jaulin, Luc; Walter, Eric (1993). 「非線形有界誤差推定のための区間解析による集合反転」(PDF) . Automatica . 29 (4): 1053–1064 . doi :10.1016/0005-1098(93)90106-4
^ Delanoue, N.; Jaulin, L.; Cottenceau, B. (2005). 「区間演算を用いた集合のパス連結性の証明」(PDF) .理論計算機科学. 351 (1).
^ Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). 「集合の連結成分の数の計算とロボット工学への応用」(PDF) .応用並列コンピューティング. 科学計算の最新技術. コンピュータサイエンス講義ノート. 第3732巻. pp. 93– 101. doi :10.1007/11558958_11. ISBN 978-3-540-29067-4。
^ Jaulin, L. (2001). 「区間とグラフを用いた経路計画」(PDF) . Reliable Computing . 7 (1).
^ Kieffer, M.; Jaulin, L.; Braems, I.; Walter, E. (2001). 「部分舗装による保証集合計算」(PDF) . Scientific Computing, Validated Numerics, Interval Methods . W. Kraemer and JW Gudenberg (Eds), Scientific Computing, Validated Numerics, Interval Methods, Kluwer Academic Publishers. pp. 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). 「部分舗装による保証集合計算」(PDF) . Scientific Computing, Validated Numerics, Interval Methods . pp. 167– 172. doi :10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8。

[2] Jaulin, Luc; Walter, Eric (1993). 「非線形有界誤差推定のための区間解析による集合反転」(PDF) . Automatica . 29 (4): 1053–1064 . doi :10.1016/0005-1098(93)90106-4

[3] Delanoue, N.; Jaulin, L.; Cottenceau, B. (2005). 「区間演算を用いた集合のパス連結性の証明」(PDF) .理論計算機科学. 351 (1).

[4] Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). 「集合の連結成分の数の計算とロボット工学への応用」(PDF) .応用並列コンピューティング. 科学計算の最新技術. コンピュータサイエンス講義ノート. 第3732巻. pp. 93– 101. doi :10.1007/11558958_11. ISBN 978-3-540-29067-4。

[5] Jaulin, L. (2001). 「区間とグラフを用いた経路計画」(PDF) . Reliable Computing . 7 (1).

[6] Kieffer, M.; Jaulin, L.; Braems, I.; Walter, E. (2001). 「部分舗装による保証集合計算」(PDF) . Scientific Computing, Validated Numerics, Interval Methods . W. Kraemer and JW Gudenberg (Eds), Scientific Computing, Validated Numerics, Interval Methods, Kluwer Academic Publishers. pp. 167– 178. doi :10.1007/978-1-4757-6484-0_14. ISBN 978-1-4419-3376-8。