Exact computation of the $2+1$ convex hull of a finite set

Pablo Angulo, Daniel Faraco, Carlos García-Gutiérrez

Published 2018-06-21Version 1

We present an algorithm to exactly calculate the $\mathbb{R}^2\oplus\mathbb{R}$-separately convex hull of a finite set of points in $\mathbb{R}^3$, as introduced in \cite{KirchheimMullerSverak2003}. When $\mathbb{R}^3$ is considered as certain subset of $3\times 2 $ matrices, this algorithm calculates the rank-one convex hull. If $\mathbb{R}^3$ is identified instead with a subset of $2\times 3$ matrices, the algorithm is actually calculating the quasiconvex hull, due to a recent result by \cite{HarrisKirchheimLin18}. The algorithm combines outer approximations based in the locality theorem \cite[4.7]{Kirchheim2003} with inner approximations to $2+1$ convexity based on "$(2+1)$-complexes". The departing point is an outer approximation and by iteratively chopping off "$D$-prisms", we prove that an inner approximation to the rank-one convex hull is reached.