{{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<br/> ''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|thumb|280px|Bracketing of the hatched set ''X'' between two subpavings. Red boxes: inner subpaving. Red and yellow: outer subpaving. The difference, 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.<ref>{{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 }}</ref>
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 <br/> ''X'' = {(''x''<sub>1</sub>, ''x''<sub>2</sub>) ∈ '''R'''<sup>2</sup> | ''x''{{su|b=1|p=2}} + ''x''{{su|b=2|p=2}} + sin(''x''<sub>1</sub> + ''x''<sub>2</sub>) ∈ [4,9]} <br/>with different accuracies. The set ''X⁻'' corresponds to red boxes and the set ''X⁺'' contains all red and yellow boxes.
thumb|Subpavings which bracket a set with a low resolution thumb|Subpavings which bracket the same set with a moderate resolution thumb|Subpavings which bracket the set with a high resolution
Combined with interval-based methods, subpavings are used to approximate the solution set of non-linear problems such as set inversion problems.<ref> {{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}} </ref> Subpavings can also be used to prove that a set defined by nonlinear inequalities is path connected,<ref> {{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}} </ref> to provide topological properties of such sets,<ref> {{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}} </ref> to solve piano-mover's problems<ref> {{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}} </ref> or to implement set computation.<ref> {{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}} </ref>
==References== {{Reflist|2}}
Category:Topology Category:Geometry