A linear optimization oracle for zonotope computation

A class of counting problems asks for the number of regions of a central hyperplane arrangement. By duality, this is the same as counting the vertices of a zonotope. Efficient algorithms are known that solve this problem by computing the vertices of a zonotope from its set of generators. Here, we give an efficient algorithm, based on a linear optimization oracle, that performs the inverse task and recovers the generators of a zonotope from its set of vertices. We also provide a variation of that algorithm that allows to decide whether a polytope, given as its vertex set, is a zonotope and when it is not a zonotope, to compute its greatest zonotopal summand.