Signed tropical convexity

Convexity for the max-plus algebra has been studied from different directions including discrete geometry, scheduling, computational complexity. As there is no inverse for the max-operation, this used to rely on an implicit non-negativity assumption. We remove this restriction by introducing ’signed tropical convexity‘. This allows to exhibit new phenomena at the interplay between computational complexity and geometry. We compare it with the discrete structure of classical polytopes and thereby highlight the differences with convexity over the signed tropical numbers. We finish with an overview of several natural formulations in terms of balance relations, polytopes over Puiseux series and hyperoperations.