Some topological properties of support points of convex sets

It is shown, as a corollary to Trojanski’s renorming theorem, that the set of support points (of certain closed convex sets) is connected. Some connectedness properties are established for support functionals, and it is also shown that the support points form an F_σ.     

Interior points of convex hulls

If a setX ⊂E ⁿ has non-emptyk-dimensional interior, or if some point isk-dimensional surrounded, then the classic theorem of E. Steinitz may be extended. For example ifX ⊂E ⁿ has int _k X ≠ 0, (0 ≦k≦n) and ifp ɛ int conX, thenp ɛ int conY for someY ⊂X with cardY≦2n−k+1.     

Approximating largest convex hulls for imprecise points

Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.     

On distance sets of large sets of integer points

Distance sets of large sets of integer points are studied in dimensions at least 5. To any ε > 0 a positive integer Q _ɛ is constructed with the following property; If A is any set of integer points of upper density at least ε, then all large multiples of Q _ɛ ² occur as squares of distances between the points of the set A. Research supported in part by NSF Grant DMS-0456490.     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

Some properties of convex hulls generated by homogeneous Poisson point processes in an unbounded convex domain

LetC(A) be the convex hull generated by a Poisson point process in an unbounded convex setA. A representation ofAC(A) as the union of curvilinear triangles with independent areas is established. In the case whenA is a cone the properties of the representation are examined more completely. It is also indicated how to simulateC(A) directly without first simulating the process itself.     

Divisible points of compact convex sets

By associating with an affine dependence the resultant of a related probability measure, we are able to define the set ofdivisible points, D(K), of a compact convex setK. Some general properties ofD(K) are discussed, and its equivalence with a set recently introduced by Reay for convex polytopes demonstrated. For polytopes,D(K) is a continuous image of a projective space. A conjecture concerningD(K) is settled affirmatively for cubes.     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

A convex sets in general position

The notion of convex cones in general position has turned out to be useful in convex programming theory. In this paper we extend the notion to convex sets and give some characterizations which yield a better insight into this concept. We also consider the case of convex sets in S-general position.     

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.     

Support functions of general convex sets

No Abstract. .In Memory of Gian-Carlo Rota