Subpaving
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.
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.
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.
01Example
The three figures on the right below show an approximation of the set
X = {(x1, x2) ∈ R2 | x2
1 + x2
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. Subpavings can also be used to prove that a set defined by nonlinear inequalities is path connected, to provide topological properties of such sets, to solve piano-mover's problems or to implement set computation.
Sources and credits
This article is adapted from the Wikipedia article “Subpaving”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Rectangular-covering.png by Krauss, CC0
- Wiki subpaving1.png by Luc Jaulin, CC BY-SA 3.0
- Wiki subpaving2.png by Luc Jaulin, CC BY-SA 3.0
- Wiki subpaving3.png by Luc Jaulin, CC BY-SA 3.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.