# Subpaving

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Subpaving
> Markdown URL: https://mediated.wiki/source/Subpaving.md
> Source: https://en.wikipedia.org/wiki/Subpaving
> Source revision: 1215209219
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Geometrical object}}
In [mathematics](/source/mathematics), a '''subpaving''' is a set of nonoverlapping [boxes](/source/hyperrectangle) of '''R⁺'''. A [subset](/source/subset) ''X'' of '''Rⁿ''' can be approximated by two subpavings ''X⁻'' and ''X⁺'' such that<br/> &nbsp;''X⁻''&thinsp;⊂&thinsp;''X''&thinsp;⊂&thinsp;''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](/source/tessellation) 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](/source/Complement_(set_theory)), outer minus inner, is a [boundary](/source/Boundary_(topology)) approximation.]]

Boxes present the advantage of being very easily manipulated by computers, as they form the heart of [interval analysis](/source/Interval_arithmetic). 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](/source/computation), a well-known application of subpaving in '''R²''' is the [Quadtree data structure](/source/Quadtree). In [image tracing](/source/image_tracing) context and other applications is important to see ''X⁻''  as [topological interior](/source/Interior_(topology)), as illustrated.

== Example ==
The three figures on the right below show an approximation of the set <br/> &nbsp; ''X'' = {(''x''<sub>1</sub>, ''x''<sub>2</sub>)&nbsp;∈&nbsp;'''R'''<sup>2</sup> | ''x''{{su|b=1|p=2}} + ''x''{{su|b=2|p=2}} + 
sin(''x''<sub>1</sub>&thinsp;+&nbsp;''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](/source/Interval_arithmetic), subpavings are used to approximate the solution set of non-linear problems such as [set inversion problems](/source/set_inversion).<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](/source/inequality_(mathematics)) is [path connected](/source/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](/source/topology) 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](/source/Motion_planning)<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

---
Adapted from the Wikipedia article [Subpaving](https://en.wikipedia.org/wiki/Subpaving) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Subpaving?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.