Efficient Geometric Operations on Convex Polyhedra

Authors: Willem Hagemann

Publish Date: 2015/09/23

Volume: 9, Issue: 3, Pages: 283-325

PDF Link

Abstract

We present a novel representation class for closed convex polyhedra where a closed convex polyhedron is represented in terms of an orthogonal projection of a higher dimensional mathcalHpolyhedron The idea is to treat the pair of the projection and the polyhedron symbolically rather than to compute the actual described polyhedron We call this representation a symbolic orthogonal projection or a sop for short We show that fundamental geometrical operations like affine transformations intersections Minkowski sums and convex hulls can be performed by simple block matrix operations on the representation Due to the underlying mathcalHpolyhedron linear programs can be used to evaluate sops eg the usage of template matrices easily yields tight overapproximations Beyond this we will also show how linear programming can be used to improve these overapproximations by adding additional supporting halfspaces or even facetdefining halfspaces to the overapproximation On the other hand we will also discuss some drawbacks of this representation eg the lack of an efficient method to decide whether one sop is a subset of another sop or the monotonic growth of the representation size under geometric operations The second part deals with reachability analysis of hybrid systems with continuous dynamics described by linear differential inclusions and arbitrary affine maps for discrete updates The invariants guards and sets of reachable states are given as convex polyhedra First we present a purely sopbased reachability algorithm where various geometric operations are performed exactly Due to the monotonic growth of the representation size of the sops this algorithm is not suited for practical applications Then we propose a combination of the sopbased algorithm with a support function based reachability algorithm Accompanied by some simple examples we show that this combination results in an efficient reachability algorithm of better accuracy than pure support function based algorithm We also discuss the current limitations of the proposed techniques and chart a path forward which might help us to solve linear programs over huge sops

Keywords: