subpaving
{{Short description|Geometrical object}}
In mathematics, a subpaving is a set of nonoverlapping boxes of R⁺. A subset X of Rⁿ can be approximated by two subpavings X⁻ and X⁺ such that
X⁻ ⊂ X ⊂ X⁺.
In R¹ the boxes are line segments, in R² rectangles and in Rⁿ hyperrectangles. A R² subpaving can be also a "non-regular tiling by rectangles", when it has no holes.
File:Rectangular-covering.png, outer minus inner, is a boundary approximation.]]
Boxes present the advantage of being very easily manipulated by computers, as they form the heart of interval analysis. Many interval algorithms naturally provide solutions that are regular subpavings.{{cite book|last1=Kieffer|first1=M.|last2=Braems|first2=I.|last3=Walter|first3=É.|last4=Jaulin|first4=L.|title=Scientific Computing, Validated Numerics, Interval Methods |chapter=Guaranteed Set Computation with Subpavings |year=2001|pages=167–172|doi=10.1007/978-1-4757-6484-0_14|isbn=978-1-4419-3376-8 |chapter-url=https://hal.archives-ouvertes.fr/hal-00845053/file/Scan2000_KIEFFER.pdf }}
In computation, a well-known application of subpaving in R² is the Quadtree data structure. In image tracing context and other applications is important to see X⁻ as topological interior, as illustrated.
Example
The three figures on the right below show an approximation of the set
X = {(x1, x2) ∈ R2 | x{{su|b=1|p=2}} + x{{su|b=2|p=2}} +
sin(x1 + x2) ∈ [4,9]}
with different accuracies. The set X⁻ corresponds to red boxes and the set X⁺ contains all red and yellow boxes.
Combined with interval-based methods, subpavings are used to approximate the solution set of non-linear problems such as set inversion problems.
{{cite journal|last1=Jaulin|first1=Luc|last2=Walter|first2=Eric|title=Set inversion via interval analysis for nonlinear bounded-error estimation|journal=Automatica|year=1993|volume=29|
issue=4|pages=1053–1064|url=http://www.ensta-bretagne.fr/jaulin/paper_automatica93.pdf
|doi=10.1016/0005-1098(93)90106-4}}
Subpavings can also be used to prove that a set defined by nonlinear inequalities is path connected,
{{cite journal|last1=Delanoue|first1=N.|last2=Jaulin|first2=L.|last3=Cottenceau|first3=B.|
title=Using interval arithmetic to prove that a set is path-connected|journal=Theoretical Computer Science |year=2005|volume=351|issue=1|url=http://www.ensta-bretagne.fr/jaulin/proving_path_connected.pdf}}
to provide topological properties of such sets,
{{cite book|last1=Delanoue|first1=N.|last2=Jaulin|first2=L.|last3=Cottenceau|first3=B.|title=Applied Parallel Computing. State of the Art in Scientific Computing |chapter=Counting the Number of Connected Components of a Set and Its Application to Robotics |series= Lecture Notes in Computer Science|year=2006|volume=3732|pages=93–101|chapter-url=http://www.ensta-bretagne.fr/jaulin/delanoueCounting.pdf|doi=10.1007/11558958_11|isbn=978-3-540-29067-4}}
to solve piano-mover's problems
{{cite journal|last=Jaulin|first=L.|
title=Path planning using intervals and graphs|journal=Reliable Computing|year=2001|volume=7|issue=1|url=http://www.ensta-bretagne.fr/jaulin/paper_cameleon.pdf}}
or to implement set computation.
{{cite book|last1=Kieffer|first1=M.|last2=Jaulin|first2=L.|last3=Braems|first3=I.
|last4=Walter|first4=E.|title=Scientific Computing, Validated Numerics, Interval Methods |chapter=Guaranteed Set Computation with Subpavings |
publisher= In W. Kraemer and J. W. Gudenberg (Eds), Scientific Computing, Validated Numerics, Interval Methods, Kluwer Academic Publishers|pages=167–178|year=2001|chapter-url=https://hal.archives-ouvertes.fr/hal-00845053/file/Scan2000_KIEFFER.pdf|doi=10.1007/978-1-4757-6484-0_14|isbn=978-1-4419-3376-8}}