Sufficiency of polyhedral surfaces in the modulus method and removable sets

The sufficiency of a family of polyhedral surfaces for calculating the modulus of a family of surfaces separating the plates of a condenser in an open set is proved. Geometric properties of removable sets for this modulus are also determined.     

Representations of polytopes and polyhedral sets

In this paper we describe a variant of the diagram techniques, such as Gale diagrams for polytopes and positive diagrams for positive bases, which is appropriate for polyhedral sets. We obtain our new technique as a translation-invariant representation of polytopes or polyhedral sets. This approach leads naturally to simpler proofs of the familiar combinatorial diagram relationships. However, this method is more versatile than those previously employed, in that it can be used to investigate linear systems of polyhedral sets, and metrical properties such as volume. In particular, we give an easy proof of a result of Meyer on decomposability of polytopes, and a more perspicuous way of looking at the well-known theorem of Minkowski on the realizability of polytopes whose facets have given outer normal vectors and areas.     

Minimal representation of convex polyhedral sets

A system of linear inequality and equality constraints determines a convex polyhedral set of feasible solutionsS. We consider the relation of all individual constraints toS, paying special attention to redundancy and implicit equalities. The main theorem derived here states that the total number of constraints together determiningS is minimal if and only if the system contains no redundant constraints and/or implicit equalities. It is shown that the existing theory on the representation of convex polyhedral sets is a special case of the theory developed here.The author is indebted to Dr. A. C. F. Vorst (Erasmus University, Rotterdam, Holland) for stimulating discussions and comments, which led to considerable improvements in many proofs. Most of the material in this paper originally appeared in the author's dissertation (Ref. 1). The present form was prepared with partial support from a NATO Science Fellowship for the Netherlands Organization for the Advancement of Pure Research (ZWO) and a CORE Research Fellowship.     

On a property of polyhedral sets

The following result is proved using solvability and optimality criteria for linear programs. The duals to the cones of feasible directions at vertices of a polyhedral set constitute a partition of the dual to the recession cone of the set.     

Generalized capacities and polyhedral surfaces

In the paper, the theory of extremal length of vector measures is used to show that the generalized condenser capacity in the sense of Aikawa and Ohtsuka is related to the module of the family of surfaces separating the condenser’s plates and disjoint with a given set. It is proved that the system of polyhedral surfaces from the above family is sufficient for approximating the module of this family. Bibliography: 17 titles.     

Locating minimal sets using polyhedral cones

In this paper, we develop a theory of localization for minimal sets of a family S of nonempty subsets of Rⁿ by considering polyhedral cones. To this end, we consider the first method to locate all efficient points of a nonempty set A⊂Rⁿ introduced by Yu (1974) [10].     

On variational inequalities over polyhedral sets

Mathematical Programming - The results on regularity behavior of solutions to variational inequalities over polyhedral sets proved in a series of papers by Robinson, Ralph and Dontchev-Rockafellar...     

Computing compromise sets in polyhedral framework

In this note, we describe the compromise set for a special polyhedral convex feasible set. This procedure gives the monotonicity of the compromise set. This scenario appears in some engineering and economic applications like the determination of the consumer's equilibrium.     

Circle packings and polyhedral surfaces

Given a triangulated surface, a euclidean or hyperbolic polyhedral surface can be constructed by assigning radii to the vertices of the triangulation. We develop necessary and sufficient conditions for the existence of such a polyhedral surface having specified characteristics. The results in this paper are included in the author's doctoral dissertation [12].     

Separating families for semi-algebraic sets

A new invariantp(V) is defined for real algebraic varietiesV which measures the complexity of semi-algebraic sets inV.p(V) is the least integer such that every semi-algebraic setS ?-V can be separated from its compliment byp(V) polynomials. This is a very natural invariant to consider. Using results of Bröcker [4–8] and generalizations of Bröcker’s results found in [16,17], upper bounds forp(V) are computed. The proof is simpler than the proof of similar results in [5–9],[15–18] since the complicated local-global formula for the stability index and the various pasting techniques are not needed. Lower bounds forp(V) are also computed in some special cases, the technique here being to first study the corresponding invariantp(X, G) for a finite space of orderings (X, G) [13,14].     

Binary extended formulations of polyhedral mixed-integer sets

We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.     

Hyperbolic polyhedral surfaces with regular faces

We study hyperbolic polyhedral surfaces with faces isometric to regular hyperbolic polygons satisfying that the total angles at vertices are at least 2π. The combinatorial information of these surfaces is shown to be identified with that of Euclidean polyhedral surfaces with negative combinatorial curvature everywhere. We prove that there is a gap between areas of non-smooth hyperbolic polyhedral surfaces and the area of smooth hyperbolic surfaces. The numerical result for the gap is obtained for hyperbolic polyhedral surfaces, homeomorphic to the double torus, whose 1-skeletons are cubic graphs.     

Separating convex sets by straight lines

We answer some questions of Tverberg about separability properties of families of convex sets. In particular, we show that there is a family of infinitely many pairwise disjoint closed disks, no two of which can be separated from two others by a straight line. No such construction exists with equal disks. We also prove that every uncountable family of pairwise disjoint convex sets in the plane has two uncountable subfamilies that can be separated by a straight line.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Note on prime representations of convex polyhedral sets

Consider a convex polyhedral set represented by a system of linear inequalities. A prime representation of the polyhedron is one that contains no redundant constraints. We present a sharp upper bound on the difference between the cardinalities of any two primes.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A8807, A4625, and A7742.