A Note on the Inversion Join for Polyhedral Analysis
Axel Simon · Electronic Notes in Theoretical Computer Science · 2010
Linear invariants are essential in many optimization and verification tasks. The domain of convex polyhedra (sets of linear inequalities) has the potential to infer all linear relationships. Yet, it is rarely applied to larger problems due to the join operation whose most precise result is given by the convex hull of two polyhedra which, in turn, may be of exponential size. Recently, Sankaranarayanan et al. proposed an operation called inversion join to efficiently approximate the convex hull. While their proposal has an ad-hoc flavour, we show that it is quite principled and, indeed, complete for planar polyhedra and, for general polyhedra, complete on over 70% of our benchmarks.