In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a subpaving is a set of nonoverlapping
boxes of R⁺. A
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''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
Interval arithmetic (also known as interval mathematics, interval analysis, or interval computation) is a mathematical technique used to Floating point error mitigation, put bounds on rounding errors and measurement errors in numerical analysis ...
. Many interval algorithms naturally provide solutions that are regular subpavings.
In
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
, a well-known application of subpaving in R² is the
Quadtree data structure. In
image tracing
In computer graphics, image tracing, raster-to-vector conversion or raster vectorization is the conversion of raster graphics into vector graphics.
Background
An image does not have any structure: it is just a collection of marks on paper, grain ...
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'' =
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
Inequality may refer to:
Economics
* Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy
* Economic inequality, difference in economic well-being between population groups
* ...
is
path connected
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets. Connectedness is one of the principal topological properties that ...
,
to provide
topological
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing h ...
properties of such sets,
to solve
piano-mover's problems
or to implement set computation.
[
]
References
{{Reflist, 2
Topology
Geometry