Extremal convex sets

Letf be an extended real valued function on the classK ⁿ of closed convex subsets of euclideann-dimensional space. A setK∈K ⁿ is said to bef-maximal if the conditionsK′∈K ⁿ ,K?K′,K≠K′ implyf(K)<f(K′), andf-minimal ifK′∈K ⁿ,K′∈K,K′≠K impliesf(K′)<f(K). In the cases whenf is the circumradius or inradius allf-maximal andf-minimal sets are determined. Under a certain regularity assumption a corresponding result is obtained for the minimal width. Moreover, a general existence theorem is established and a result concerning the existence of extremal sets with respect to packing and covering densities is proved.     

Almost convex sets

The concept of a wedgoid, a generalized wedge, is introduced and studied. Almost all convex sets are characterized by the fact that balls can be separated from such a set by means of wedgoids.     

Nine convex sets determine a pentagon with convex sets as vertices

It is proved that if ℱ is a family of nine pairwise disjoint compact convex sets in the plane such that no member of ℱ is contained in the convex hull of the union of two other sets of ℱ, then ℱ has a subfamily ℱ′ with five elements such that no member of ℱ′ is contained in the convex hull of the union of the other sets of ℱ′.     

Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Infinite dimensional convex sets with a property common to finite dimensional convex sets

We characterize those metrizable compact convex sets K that contain a Bauer simplex B such that any two affine continuous functions on K coinciding on B are equal; further, we show that all metrizable simplexes and dual balls of separable L¹-preduals have this property.     

Semidefinite representation of convex sets

Let be a semialgebraic set defined by multivariate polynomials g _i (x). Assume S is convex, compact and has nonempty interior. Let , and ∂ S (resp. ∂ S _i ) be the boundary of S (resp. S _i ). This paper, as does the subject of semidefinite programming (SDP), concerns linear matrix inequalities (LMIs). The set S is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex S may not be LMI representable (Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007). A question arising from Nesterov and Nemirovski (SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994), see Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007 and Nemirovski in Plenary lecture, International Congress of Mathematicians (ICM), Madrid, Spain, 2006, is: given a subset S of , does there exist an LMI representable set Ŝ in some higher dimensional space whose projection down onto equals S. Such S is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. The following are the main contributions of this paper: (i) assume g _i (x) are all concave on S. If the positive definite Lagrange Hessian condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function ℓ ^T x on S is positive definite at the minimizer, then S is SDP representable. (ii) If each g _i (x) is either sos-concave ( − ∇² g _i (x) = W(x) ^T W(x) for some possibly nonsquare matrix polynomial W(x)) or strictly quasi-concave on S, then S is SDP representable. (iii) If each S _i is either sos-convex or poscurv-convex (S _i is compact convex, whose boundary has positive curvature and is nonsingular, i.e., ∇g _i (x) ≠ 0 on ∂ S _i ∩ S), then S is SDP representable. This also holds for S _i for which ∂ S _i ∩ S extends smoothly to the boundary of a poscurv-convex set containing S. (iv) We give the complexity of Schmüdgen and Putinar’s matrix Positivstellensatz, which are critical to the proofs of (i)–(iii).      

Nonoscillation theorems in convex sets

This paper presents a new and simple technique for a certain class of variational problems which includes many of the important problems of mathematical physics, e.g., the Brachistochrone, geodesies, and minimal surface of revolution problems. The technique uses Caratheodory's equivalent problems approach but combines two equivalent problems at the same time to get the sufficiency and uniqueness results. It does not use any of the classical sufficiency conditions such as the Weierstrass condition. The equations that we are led to by this new approach turn out to be the Hamilton-Jacobi and Euler-Lagrange equations for the problem, but here we have not had to use any of the classical Hamilton-Jacobi theory nor derivations to get its results (e.g., orthogonality of the extremals to the wave fronts) for this class of problems. The cases for one and n dependent variables are presented and illustrated. Implications and generalizations of the method are discussed.     

Continuous valuations on convex sets

((Without abstract)) Submitted: December 1997     

Stochastic viability of convex sets

We investigate necessary and sufficient conditions for viability of a closed convex set K under weak solutions of a stochastic differential equation. These conditions are expressed in terms of the distance function to K. When in addition the boundary of K is smooth, then our necessary and sufficient conditions reduce to two relations that have to be verified just on the boundary of K.