On the enumeration of convex polyhedra

We state and justify an asymptotic formula for the number of combinatorially distinct convex polyhedra with 2n faces, all triangular.     

The asymptotic enumeration of rooted convex polyhedra

An asymptotic formula is obtained for the number of rooted c-nets with m vertices and n edges as m, n → ∞ with $\text{1}\text{2}\text{+ ε <}\text{n}\text{m}\text{< 2 ? ε}$ for some ε > 0.     

A constant-time parallel algorithm for computing convex hulls

The convex hull of a finite set of points in the plane can be computed in constant time using a polynomial number of processors.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC - A3336.     

An improved vertex enumeration algorithm

The main computational burden in pivoting methods for determining all vertices of a convex polytope appears to be in testing pairs of vertices for adjacency. We show how, in the Dyer-Proll algorithm, this burden can be reduced by a new labelling of the search tree and by a mechanism for removing redundant branches. We also introduce an implementation strategy, the barred pivot strategy, which further improves the algorithm's performance.     

A conjecture on convex polyhedra

We select a class of pyramids of a particular shape and propose a conjecture that precisely these pyramids are of greatest surface area among the closed convex polyhedra having evenly many vertices and the unit geodesic diameter. We describe the geometry of these pyramids. The confirmation of our conjecture will solve the “doubly covered disk” problem of Alexandrov. Through a connection with Reuleaux polygons we prove that on the plane the convex n-gon of unit diameter, for odd n, has greatest area when it is regular, whereas this is not so for even n.     

An algorithm for determining redundant inequalities and all solutions to convex polyhedra

Given a system of linear inequalities that define a polyhedral cone, we develop a simple technique for finding redundant inequalities. We thus insure that only the cone's extreme rays are calculated. The general solution for the system is developed in terms of the extreme rays. The method leads directly to the general solution for either bounded or unbounded polyhedra.     

Limit theorems for convex hulls

It is shown that the process of vertices of the convex hull of a uniform sample from the interior of a convex polygon converges locally, after rescaling, to a strongly mixing Markov process, as the sample size tends to infinity. The structure of the limiting Markov process is determined explicitly, and from this a central limit theorem for the number of vertices of the convex hull is derived. Similar results are given for uniform samples from the unit disk.     

A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement.     

A generalized complementary pivoting algorithm

Complementary pivot algorithms known at the present time fall into several quite general categories, with obvious similarities. This paper deals with general pivoting systems which provide a natural setting for the study of complementary pivot algorithms. A generalized algorithm is presented for these systems. We give results on the number of iterations necessary for such an algorithm.This paper is based on the author's doctoral dissertation for the Department of Administrative Sciences, Yale University. The author would like to thank his advisors, Professors G.H. Bradley, D. Brown and N. White. This research was supported in part by National Science Foundation grants GK-13757 and GP-32158X.     

An algorithm for the construction of convex hulls in simple integer recourse programming

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.     

A complementary pivoting algorithm for linear network problems

In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal, and Schneider for solving singlecommodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in which a sequence of subproblems is formed by solving the problem ‘one-node-at-a-time’. The algorithm is tested on uncapacitated transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm is implemented in C under UNIX), the results show that the method is very effective and may be competitive with the best available algorithms for linear network problems. This research was supported, in part, by grant number ECS-8504195 from the National Science Foundation.     

Limit theorems for functionals of convex hulls

Summary In [4] a central limit theorem for the number of vertices of the convex hull of a uniform sample from the interior of a convex polygon is derived. This is done by approximating the process of vertices of the convex hull by the process of extreme points of a Poisson point process and by considering the latter process of extreme points as a Markov process (for a particular parametrization). We show that this method can also be applied to derive limit theorems for the boundary length and for the area of the convex hull. This extents results of Rényi and Sulanke (1963) and Buchta (1984), and shows that the boundary length and the area have a strikingly different probabilistic behavior.     

An improved N-tree algorithm for the enumeration of all neighbors of a degenerate vertex

Based on the concept of degeneracy graphs, theoretical and algorithmic aspects of the neighborhood-problem are dealt with. It is shown that any subgraph of a positive degeneracy graph which is induced by a set of nodes feasible with respect to an arbitrary lexicographic pivot selection will supply sufficient information. A special lexicographic pivot selection strategy is presented which leads to an improved version of the N-tree method. The increase in efficiency is illustrated by test results.