The Complexity of Vertex Enumeration Methods
Mathematics of Operations ResearchPublished 1 August 1983
Martin Dyer
Citations180
SJR quartileQ1
SJR score1.35
SNIP1.90
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new algorithm is described, and shown to have a better complexity estimate than existing methods and theoretical superiority, and empirical evidence supporting the theoretical superiority is presented.
Abstract
The computational complexity of problems relating to the enumeration of all the vertices of a convex polyhedron defined by linear inequalities is examined. Several published approaches are evaluated in this light. A new algorithm is described, and shown to have a better complexity estimate than existing methods. Empirical evidence supporting the theoretical superiority is presented. Finally vertex enumeration is discussed when the space containing the polyhedra is of fixed dimension and only the size of the inequality system is permitted to vary.
Keywords
Computer ScienceMathematics
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Theoretical Computer ScienceThe complexity of computing the permanent
2,759 Citations1979Leslie G. Valiant
It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations.
SIAM Journal on ComputingThe Complexity of Enumeration and Reliability Problems
2,086 Citations1979Leslie G. Valiant
For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems.
Sorting and Searching
1,536 Citations1973Donald E. Knuth
Communications of the ACMConvex hulls of finite sets of points in two and three dimensions
706 Citations1977F. P. Preparata, S. J. Hong
The presented algorithms use the “divide and conquer” technique and recursively apply a merge procedure for two nonintersecting convex hulls to ensure optimal time complexity within a multiplicative constant.
ACM SIGACT NewsBig Omicron and big Omega and big Theta
593 Citations1976Donald E. Knuth
I have recently asked several prominent mathematicians if they knew what ~(n 2) meant, and more than half of them had never seen the notation before, so I decided to search more carefully, and to study the history of O-notation and o-notation as well.
Theoretical Computer ScienceFinding the intersection of two convex polyhedra
292 Citations1978David E. Muller, F. P. Preparata
An algorithm to test whether their intersection is empty, and if so to find a separating plane, and to construct their intersection polyhedron is developed, which runs in timeO (n log n), where n is the sum of the numbers of vertices of the two polyhedra.
ACM Transactions on Mathematical SoftwareA New Convex Hull Algorithm for Planar Sets
285 Citations1977William F. Eddy
A new algorithm, CONVEX, that determines which points of a planar set are vertices of the convex hull of the set is presented and it is shown thatCONVEX operates in a fashion similar to the sorting algorithm QUICKERSORT.
Geometric complexity
264 Citations1975Michael Ian Shamos
An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.
Mathematics of Operations ResearchA Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
247 Citations1980T. H. Matheiss, David S. Rubin
This paper surveys the literature on methods for finding all vertices of convex polytopes, contrasting the main features of each method and providing computational results for representative methods.
Journal of the Society for Industrial and Applied MathematicsAn Algorithm for Finding All Vertices of Convex Polyhedral Sets
184 Citations1961M. L. Balinski
Communications of the ACMAn optimal real-time algorithm for planar convex hulls
125 Citations1979F. P. Preparata
An algorithm is described for the construction in real-time of the convex hull of a set of set of points in the plane by successive updates, thereby achieving a total processing time of O(n)(log log log) for this model.
Operations ResearchAn Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
120 Citations1973T. H. Mattheiss
A new method of generating all vertices of a given convex polytope is described, which embeds the givenpolytope in a one-higher-dimensional space and associates a number with each interior point that facilitates the construction of a spanning tree for all of the interior points.
Israel Journal of MathematicsThe minimum number of vertices of a simple polytope
106 Citations1971David Barnette
Mathematical ProgrammingAn algorithm for determining all extreme points of a convex polytope
100 Citations1977Martin Dyer, L. G. Proll
An algorithm for determining all the extreme points of a convex polytope associated with a set of linear constraints, via the computation of basic feasible solutions to the constraints, is presented.
Numerische MathematikFinding all vertices of a convex polyhedron
86 Citations1968Miroslav Maňas, Josef Nedoma
An algorithm for finding all vertices of a convex polyhedron defined by a system of linear equations and by non-negativity conditions for variables seems to provide a computationally effective method.
FACETS AND VERTICES OF TRANSPORTATION POLYTOPES
79 Citations1967Victor Klee, Christoph Witzgall
Acta MathematicaPolytope pairs and their relationship to linear programming
44 Citations1974Victor Klee
Numerische MathematikAn algorithm for determining redundant inequalities and all solutions to convex polyhedra
29 Citations1975Harold Greenberg
Information Processing LettersOn the Ω(n log n) lower bound for convex hull and maximal vector determination
27 Citations1980Peter van Emde Boas
Mathematics of Operations ResearchThe Probability that a Random Polytope is Bounded
27 Citations1977Brian K. Schmidt, T. H. Mattheiss
Results of a simulation giving i the probability that all m constraints are relevant and ii a formula for the expected number of vertices of a polytope, are presented.
SIAM Journal on Applied MathematicsGenerating All the Faces of a Polyhedron
25 Citations1974Claude‐Alain Burdet
Mathematical ProgrammingLeast distance methods for the scheme of polytopes
24 Citations1978Balder Von Hohenbalken
Methods are described and APL-codes are supplied to find vertices, edges, other faces and facets of polytopes given by point sets, i.e. quadratic, programming.
Operations ResearchTechnical Note—Vertex Generation and Cardinality Constrained Linear Programs
22 Citations1975David S. Rubin
This work shows how to solve the CCLP by modifying a procedure for generating all the vertices of the feasible region of the associated linear program.
ComputingAn algorithm for enumerating all vertices of a convex polyhedron
20 Citations1975W. Altherr
This paper describes an algorithm to enumerate these vertices of a bounded, convex polyhedronP inRn with the help of graphs and a concept by Mañas and Nedoma.
Mathematical ProgrammingComputational results on an algorithm for finding all vertices of a polytope
18 Citations1980T. H. Mattheiss, Brian K. Schmidt
Results relating to the expected properties of polytopes indicate that n-polytopes defined by “large” numbers of constraints are difficult to obtain by random processes, and the expected value of the number of vertices of polytope is considerably less than Klee's least upper bound.
Mathematical ProgrammingEliminating extraneous edges in Greenberg's algorithm
3 Citations1980Martin Dyer, L. G. Proll
A procedure for eliminating the extraneous edges of convex polyhedra found by Greenberg's method is presented and computational experience with it is reported.