A linear optimization oracle for zonotope computation

DOI10.1016/J.COMGEO.2021.101809zbMATH Open1479.52035arXiv1912.02439OpenAlexW3182641525MaRDI QIDQ824329FDOQ824329

Lionel Pournin, Antoine Deza

Publication date: 15 December 2021

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

optimization algorithmshyperplane arrangementsenumeration algorithmsMinkowski sums

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Zonotopes and the LP-Newton method
• Computing characteristic polynomials of hyperplane arrangements with symmetries

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)