Sampling-Based Polytope Calculus: Computations and Applications

Polytope calculus refers to the computation of polytopes under set operations and to algorithms for the conversion across their different representations. It is fundamental for, among other uses, reachability analysis of dynamical systems and thus, more generally, verification approaches for hybrid dynamical models. However, tackling the computational complexities inherent in polytope calculus poses challenges, since most operations exhibit exponential time complexity. In this paper, we introduce novel sampling-based algorithms to compute V-polytope representations, which provide efficient polynomial-time solutions with high approximation accuracy for common operations in polytope calculus. We show the soundness and probabilistic tightness of the sample-based approach. Following a comprehensive evaluation, we highlight the superior performance of the proposed algorithms in comparison to existing approaches, both in terms of scalability and approximation quality. We further develop a new verification-based method to compute an under-approximate H-polytope from a V-polytope representation, which complements the sampling-based algorithm for polytope calculus. We finally showcase their practical relevance in case studies concerning computation of invariant sets and reachability analysis for dynamical systems, thus demonstrating the effectiveness of the proposed approach.