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.     

Protecting convex sets

A point-setS is protecting a collection F =T ₁,T ₂,..., _n ofn mutually disjoint compact sets if each one of the setsT _i is visible from at least one point inS; thus, for every setT _i ∈F there are points xS andy T _i such that the line segment joining x to y does not intersect any element inF other thanT _i . In this paper we prove that [2(n-2)/3] points are always sufficient and occasionally necessary to protect any family F ofn mutually disjoint compact convex sets. For an isothetic family F, consisting ofn mutually disjoint rectangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary to protect it. IfF is a family of triangles, [4n/7] points are always sufficient. To protect families ofn homothetic triangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary.     

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.     

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.     

Shadow systems of convex sets

Ans-system of convex sets is the system of shadows of a given convex set cast on to a subspace by a beam of light whose direction varies. Here the convexity properties ofs-systems are investigated, and, in the final section, a relationship with the projection functions of convex sets is established.     

Typical property of convex sets

Translated from Matematicheskie Zametki, Vol. 49, No. 2, pp. 107–112, February, 1991.     

Seminormality properties of convex sets

In discussing Lagrange problems of optimal control for simple as well as for multiple integrals Cesari has introduced an upper semicontinuity property of variable sets called property (Q) which plays a role analogous to that of Tonelli's and McShane's concept, of seminormality for free problems of the calculus of variations. This paper deals with analytical criteria for property (Q) which is the unifying idea in the study of lower semicontinuity and lower closure with unbounded controls. In section 1 we state the concepts of seminormality, normality, and property (Q). In section 2 we establish new criteria for property (Q) in the particular situation whenf ₀(t,x,u) is continuous and seminormal (or normal) andf(t,x,u) is linear in the variableu. In section 3 we consider the role of property (Q) for restricted sets. In section 4 we discuss the intermediate properties (Q _p).     

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).