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 …