Topological convexities, selections and fixed points

A convexity on a set X is a family of subsets of X which contains the whole space and the empty set as well as the singletons and which is closed under arbitrary intersections and updirected unions. A uniform convex space is a uniform topological space endowed with a convexity for which the convex hull operator is uniformly continuous. Uniform convex spaces with homotopically trivial polytopes (convex hulls of finite sets) are absolute extensors for the class of metric spaces; if they are completely metrizable then a continuous selection theorem à la Michael holds. Upper semicontinuous maps have approximate selections and fixed points, under the usual assumptions.     

Choice,hull, continuity and fidelity

Continuity and fidelity (i.e., ‘path-independence’) conditions are studied for choices (picking subsets), hulls (picking supersets) and compositions of these. Examples of hulls are topological closure and convex hull, both of which are faithful. Using a continuity theorem of Sertel, a sufficient condition is given for closed convex hull, d, to be both continuous and faithful on the space of compact subsets of a locally convex topological vector space. A sufficient condition is also given for the joint continuity and fidelity of the composition, sd, of a choice, s, and d. In contrast with the Kalai and Megiddo theorem that singleton-valued maps of this form cannot be faithful and at the same time continuous on the space of finite subsets of Eⁿ, the conjunction of (upper semi-)continuity and fidelity is shown to be commonplace for choices or maps of the above form (not constrained to be singleton-valued).     

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.

     

Convex hull of Brownian motion ind-dimensions

We supposeK(w) to be the boundary of the closed convex hull of a sample path ofZ _t(w), 0 ≦t ≦ 1 of Brownian motion ind-dimensions. A combinatorial result of Baxter and Borndorff Neilson on the convex hull of a random walk, and a limiting process utilizing results of P. Levy on the continuity properties ofZ _t(w) are used to show that the curvature ofK(w) is concentrated on a metrically small set.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

Properties of vertex packing and independence system polyhedra

We consider two convex polyhedra related to the vertex packing problem for a finite, undirected, loopless graphG with no multiple edges. A characterization is given for the extreme points of the polyhedron \(\mathcal{L}_G = \{ x \in R^n :Ax \leqslant 1_m ,x \geqslant 0\} \) , whereA is them × n edge-vertex incidence matrix ofG and 1 _m is anm-vector of ones. A general class of facets of = convex hull{x∈R ⁿ :Ax≤1 _m ,x binary} is described which subsumes a class examined by Padberg [13]. Some of the results for are extended to a more general class of integer polyhedra obtained from independence systems.     

Hereditary order convexity inL(X,Y)

LetX be a topological vector space,Y an ordered topological vector space andL(X,Y) the space of all linear and continuous mappings fromX intoY. The hereditary order-convex cover [K] ^h of a subsetK ofL(X,Y) is defined by [K] ^h ={A∈L(X,Y):Ax∈[Kx] for allx∈X}, where[Kx] is the order-convex ofKx. In this paper we study the hereditary order-convex cover of a subset ofL(X,Y). We show how this cover can be constructed in specific cases and investigate its structural and topological properties. Our results extend to the spaceL(X,Y) some of the known properties of the convex hull of subsets ofX ^*.     

Wijsman topology on function spaces

LetC(X,Y) be the space of continuous functions from a metric space (X,d) to a metric space (Y, e).C(X, Y) can be thought as subset of the hyperspaceCL(X×Y) of closed and nonempty subsets ofX×Y by identifying each element ofC(X,Y) with its graph. We considerC(X,Y) with the topology inherited from the Wijsman topology induced onCL(X×Y) by the box metric ofd ande. We study the relationships between the Wijsman topology and the compact-open topology onC(X,Y) and also conditions under which the Wijsman topology coincide with the Fell topology. Sufficient conditions under which the compactopen topology onC(X,Y) is weaker than the Wijsman topology are given (IfY is totally bounded, then for every metric spaceX the compactopen topology onC(X,Y) is weaker than the Wijsman topology and the same is true forX locally connected andY rim-totally bounded). We prove that a metric spaceX is boundedly compact iff the Wijsman topology onC(X, ?) is weaker than the compact-open topology. We show that ifX is a σ-compact complete metric space andY a compact metric space, then the Wijsman topology onC(X,Y) is Polish.     

k-convexn-person games and their cores

For any natural numbersk andn, the subclass ofk-convexn-person games is introduced. In casek=n, the subclass consists of the convexn-person games. Ak-convexn-person game is characterized in several ways in terms of the core and certain marginal worth vectors. The marginal worth vectors of a game are described in terms of an upper bound for the core and the corresponding gap function. It is shown that thek-convexity of ann-person gamev is equivalent to

1. all marginal worth vectors ofv belong to the core ofv; or
2. the core ofv is the convex hull of the set consisting of all marginal worth vectors ofv; or
3. the extreme points of the core ofv are exactly the marginal worth vectors ofv.

Examples ofk-convexn-person games are also treated.     

Some remarks on the Krein-Milman property and lexicographic maxima

A Banach space has thelexicographic property if each bounded closed convex subsetC is the closed convex hull of the lexicographic maxima ofC. The relationships between this property and the Radon-Nikodym and Krein-Milman properties are provided. A example inl ¹ contrasts these concepts. The main result states that a Banach space which is anr-space has the lexicographic property. Several questions relating to these topics and also flat spaces are posed.     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

On convex hulls of compact sets of probability measures with countable supports

E. Michael and I. Namioka proved the following theorem. Let Y be a convex G _δ -subset of a Banach space E such that if K ? Y is a compact space, then its closed (in Y) convex hull is also compact. Then every lower semicontinuous set-valued mapping of a paracompact space X to Y with closed (in Y) convex values has a continuous selection. E. Michael asked the question: Is the assumption that Y is G _δ essential? In this note we give an affirmative answer to this question of Michael.     

How to Exhibit Toroidal Maps in Space

Steinitz's theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the points on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.     

On the intrinsic and the spatial numerical range

For a bounded function f from the unit sphere of a closed subspace X of a Banach space Y, we study when the closed convex hull of its spatial numerical range W(f) is equal to its intrinsic numerical range V(f). We show that for every infinite-dimensional Banach space X there is a superspace Y and a bounded linear operator such that . We also show that, up to renormig, for every non-reflexive Banach space Y, one can find a closed subspace X and a bounded linear operator T∈L(X,Y) such that .Finally, we introduce a sufficient condition for the closed convex hull of the spatial numerical range to be equal to the intrinsic numerical range, which we call the Bishop-Phelps-Bollobás property, and which is weaker than the uniform smoothness and the finite-dimensionality. We characterize strong subdifferentiability and uniform smoothness in terms of this property.     

$$T_5$$-Configurations and non-rigid sets of matrices

In 2003 B. Kirchheim-D. Preiss constructed a Lipschitz map in the plane with 5 incompatible gradients, where incompatibility refers to the condition that no two of the five matrices are rank-one connected. The construction is via the method of convex integration and relies on a detailed understanding of the rank-one geometry resulting from a specific set of five matrices. The full computation of the rank-one convex hull for this specific set was later carried out in 2010 by W. Pompe in Calc. Var. PDE 37(3–4):461–473, (2010) by delicate geometric arguments. For more general sets of matrices a full computation of the rank-one convex hull is clearly out of reach. Therefore, in this short note we revisit the construction and propose a new, in some sense generic method for deciding whether convex integration for a given set of matrices can be carried out, which does not require the full computation of the rank-one convex hull.     

Steiner polygons in the Steiner problem

A polygon, whose vertices are points in a given setA ofn points, is defined to be a Steiner polygon ofA if all Steiner minimal trees forA lie in it. Cockayne first found that a Steiner polygon can be obtained by repeatedly deleting triangles from the boundary of the convex hull ofA. We generalize this concept and give a method to construct Steiner polygons by repeatedly deletingk-gons,k n. We also prove the uniqueness of Steiner polygons obtained by our method.     

Farthest points in weakly compact sets

LetS be a weakly compact subset of a Banach spaceB. We show that of all points inB which have farthest points inS contains a denseG ₅ ofB. Also, we give a necessary and sufficient condition for bounded closed convex sets to be the closed convex hull of their farthest points in reflexive Banach spaces.     

Approximation of convex bodies by polytopes

LetC be a convex body ofE ^d and consider the symmetric difference metric. The distance ofC to its best approximating polytope having at mostn vertices is 0 (1/n ^2/(d?1)) asn→∞. It is shown that this estimate cannot be improved for anyC of differentiability class two. These results complement analogous theorems for the Hausdorff metric. It is also shown that for both metrics the approximation properties of «most» convex bodies are rather irregular and that ford=2 «most» convex bodies have unique best approximating polygons with respect to both metrics.