A linear optimization oracle for zonotope computation

DOI10.1016/J.COMGEO.2021.101809MaRDI QIDQ824329zbMATH OpenOpenAlexFDO

Authors Antoine Deza, Lionel Pournin

Publication date 15 December 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.02439

zbMATH Keywords

optimization algorithmshyperplane arrangementsenumeration algorithmsMinkowski sums

Mathematics Subject Classification ID

Linear programming (90C05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: A class of counting problems ask for the number of regions of a central hyperplane arrangement. By duality, this is the same as counting the vertices of a zonotope. We give several efficient algorithms, based on a linear optimization oracle, that solve this and related enumeration problems. More precisely, our algorithms compute the vertices of a zonotope from the set of its generators and inversely, recover the generators of a zonotope from its vertices. A variation of the latter algorithm also allows to decide whether a polytope, given as its vertex set, is a zonotope and when it is not, to compute its greatest zonotopal summand.

Recommendations

• Small primitive zonotopes
• From the zonotope construction to the Minkowski addition of convex polytopes
• On the co-NP-completeness of the zonotope containment problem
• Zonotopes and the LP-Newton method
• Large-Scale Scientific Computing

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Aperiodic Tilings, Positive Scalar Curvature, and Amenability of Spaces
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Convex integer optimization by constantly many linear counterparts
• Decomposability of polytopes
• Decomposable convex polyhedra
• Diameter, decomposability, and Minkowski sums of polytopes
• Geometric algorithms and combinatorial optimization.
• How good are convex hull algorithms?
• Indecomposable Polytopes
• Indecomposable polytopes
• Pivot versus interior point methods: Pros and cons
• Primitive zonotopes
• Reverse search for enumeration
• Root cones and the resonance arrangement

Cited in

(3)

• Zonotopes and the LP-Newton method
• Computing characteristic polynomials of hyperplane arrangements with symmetries
• On the co-NP-completeness of the zonotope containment problem

This page was built for publication: A linear optimization oracle for zonotope computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q824329)