Subpaving

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.

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.^[1]

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.

^ Kieffer, M.; Braems, I.; Walter, É.; Jaulin, L. (2001). "Guaranteed Set Computation with Subpavings" (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.

[1] Kieffer, M.; Braems, I.; Walter, É.; Jaulin, L. (2001). "Guaranteed Set Computation with Subpavings" (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.

[1]