A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search

DOI10.1137/15M1027930zbMath1383.52021OpenAlexW2785447469MaRDI QIDQ4605440

Miroslav Rada, Michal Černý

Publication date: 22 February 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1027930

zbMATH Keywords

hyperplane arrangementszonotopescompact algorithmcell enumerationoutput-sensitive algorithm

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items (4)

Multivariate Estimator for Linear Dynamical Systems with Additive Laplace Measurement and Process Noises ⋮ A class of optimization problems motivated by rank estimators in robust regression ⋮ Partial identification in nonseparable binary response models with endogenous regressors ⋮ Nonparametric Maximum Likelihood Methods for Binary Response Models With Random Coefficients

Cites Work

• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• Reverse search for enumeration
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Enumerating extreme points in higher dimensions
• Output-sensitive cell enumeration in hyperplane arrangements
• Partition of Space
• A polynomial case of unconstrained zero-one quadratic optimization

This page was built for publication: A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search