An efficient algorithm for vertex enumeration of arrangement

DOI10.1016/J.DAM.2025.10.042MaRDI QIDQ6883338zbMATH OpenFDO

Authors Zelin Dong, Feng-lei Fan, Huan Xiong, Tieyong Zeng

Publication date 16 December 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.10.042

zbMATH Keywords

hyperplane arrangementpolynomial pivoting rulevertex enumeration

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Cites work

• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• A combinatorial abstraction of linear programming
• A convergent criss-cross method
• A counterexample to the Hirsch conjecture
• A finite crisscross method for oriented matroids
• A Node Method for Multiparametric Linear Programming
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A subexponential bound for linear programming
• An Algorithm for Convex Polytopes
• An algorithm for determining all extreme points of a convex polytope
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Enumeration of Nash equilibria for two-player games
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 3078984 (Why is no real title available?)
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• New Finite Pivoting Rules for the Simplex Method
• On the finiteness of the criss-cross method
• On the length of monotone paths in polyhedra
• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• Pivot rules for linear programming: A survey on recent theoretical developments
• Primal-dual methods for vertex and facet enumeration
• Random edge can be exponential on abstract cubes
• Reachability analysis of deep ReLU neural networks using facet-vertex incidence
• Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix-Vector Products
• The d-Step Conjecture and Its Relatives
• The Complexity of Vertex Enumeration Methods
• The Hirsch conjecture for the fractional stable set polytope
• The Hirsch conjecture is true for (0,1)-polytopes
• Two New Bounds for the Random‐Edge Simplex‐Algorithm

This page was built for publication: An efficient algorithm for vertex enumeration of arrangement

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