A linear optimization oracle for zonotope computation

Autor: Antoine Deza, Lionel Pournin
Přispěvatelé: Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Control and Optimization
Linear programming
Duality (mathematics)
Polytope
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
01 natural sciences
Oracle
Set (abstract data type)
Combinatorics
Mathematics - Metric Geometry
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
Mathematics - Combinatorics
Mathematics::Metric Geometry
0101 mathematics
Mathematics - Optimization and Control
ComputingMilieux_MISCELLANEOUS
Mathematics
Mathematics::Combinatorics
Mathematics::Commutative Algebra
010102 general mathematics
Metric Geometry (math.MG)
Computer Science Applications
Vertex (geometry)
Computational Mathematics
Computational Theory and Mathematics
Hyperplane
Counting problem
Optimization and Control (math.OC)
010201 computation theory & mathematics
Combinatorics (math.CO)
Geometry and Topology
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Computational Geometry
Computational Geometry, Elsevier, In press, 100, pp.101809. ⟨10.1016/j.comgeo.2021.101809⟩
ISSN: 0925-7721
DOI: 10.1016/j.comgeo.2021.101809⟩
Popis: 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.
Comment: 22 pages, 2 figures
Databáze: OpenAIRE
Externí odkaz: