overapproximation

Overapproximation is a concept in mathematics and computer science referring to an estimate that bounds the quantity of interest from above or to a set that contains the true object. In set-theoretic terms, an overapproximation of a target set S is a superset S_hat with S ⊆ S_hat. The term is often used when exact computation is intractable or when a conservative estimate is preferable to avoid missing possible values or states.

In geometry and analysis, an overapproximation provides a safe envelope around a set or solution. For example, when the exact reachable region of a dynamical system is difficult to compute, an overapproximation describes a larger, computable region that is guaranteed to contain it. In numerical contexts, overapproximation also manifests as upper bounds on errors or tolerances.

In program analysis and formal verification, over-approximations of program states (abstract interpretation) ensure soundness: every behavior that could occur in the real program is represented in the analysis. This may introduce spurious behaviors that cannot occur in execution, a trade-off that favors safety guarantees over precision. Under certain conditions, under-approximation can be used, but it risks missing feasible executions.

Representations and techniques for overapproximation include convex hulls of unions, ellipsoidal bounds, zonotopes, polyhedral abstractions, interval arithmetic, and affine arithmetic. In reachability analyses, overapproximation of the set of possible states is common to ensure that safety properties hold, with refinement (for example, via counterexample-guided abstraction refinement) used to reduce conservatism.

Applications appear in robotics, aerospace, automotive safety, and static analysis of software, where guaranteed containment of uncertainty is essential.