Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

Convex polarities over ordered fields

We use tools and methods from real algebraic geometry (spaces of ultrafilters, elimination of quantifiers) to formulate a theory of convexity in K^N over an arbitrary ordered field. By defining certain ideal points (which can be viewed as generalizations of recession cones) we obtain a generalized notion of polar set. These satisfy a form of polar duality that applies to general convex sets and does not reduce to classical duality if K is the field of real numbers. As an application we give a partial classification of total orderings of Artinian local rings and two applications to ordinary convex geometry over the real numbers.     

Normal Fans of Polyhedral Convex Sets

The normal fan of a polyhedral convex set in ? ⁿ is the collection of its normal cones. The structure of the normal fan reflects the geometry of that set. This paper reviews and studies properties about the normal fan. In particular, it investigates situations in which the normal fan of a polyhedral convex set refines, or is a subfan of, that of another set. It then applies these techniques in several examples. One of these concerns the face structure and normal manifold of the critical cone of a polyhedral convex set associated with a point in ? ⁿ . Another concerns how perturbation of the right hand side of the linear constraints defining such a set affects the normal fan and the face structure.     

Zone diagrams in compact subsets of uniformly convex normed spaces

A zone diagram is a relatively new concept which has emerged in computational geometry and is related to Voronoi diagrams. Formally, it is a fixed point of a certain mapping, and neither its uniqueness nor its existence are obvious in advance. It has been studied by several authors, starting with T. Asano, J. Matoušek and T. Tokuyama, who considered the Euclidean plane with singleton sites, and proved the existence and uniqueness of zone diagrams there. In the present paper we prove the existence of zone diagrams with respect to finitely many pairwise disjoint compact sites contained in a compact and convex subset of a uniformly convex normed space, provided that either the sites or the convex subset satisfy a certain mild condition. The proof is based on the Schauder fixed point theorem, the Curtis-Schori theorem regarding the Hilbert cube, and on recent results concerning the characterization of Voronoi cells as a collection of line segments and their geometric stability with respect to small changes of the corresponding sites. Along the way we obtain the continuity of the Dom mapping as well as interesting and apparently new properties of Voronoi cells.     

Quantum convex support

Convex support, the mean values of a set of random variables, is central in information theory and statistics. Equally central in quantum information theory are mean values of a set of observables in a finite-dimensional C^∗-algebra A, which we call (quantum) convex support. The convex support can be viewed as a projection of the state space of A and it is a projection of a spectrahedron.Spectrahedra are increasingly investigated at least since the 1990s boom in semi-definite programming. We recall the geometry of the positive semi-definite cone and of the state space. We write a convex duality for general self-dual convex cones. This restricts to projections of state spaces and connects them to results on spectrahedra.Our main result is an analysis of the face lattice of convex support by mapping this lattice to a lattice of orthogonal projections, using natural isomorphisms. The result encodes the face lattice of the convex support into a set of projections in A and enables the integration of convex geometry with matrix calculus or algebraic techniques.     

Determinantal representations and Bézoutians

A major open question in convex algebraic geometry is whether all hyperbolicity cones are spectrahedral, i.e. the solution sets of linear matrix inequalities. We will use sum-of-squares decompositions of certain bilinear forms called Bézoutians to approach this problem. More precisely, we show that for every smooth hyperbolic polynomial h there is another hyperbolic polynomial q such that \(q \cdot h\) has a definite determinantal representation. Besides commutative algebra, the proof relies on results from real algebraic geometry.     

On a cone covering problem

Given a set of polyhedral cones C₁,…,Ck⊂Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computational complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi.     

Nondegenerate families of convex cones and convex polytopes

This paper describes relations between convex polytopes and certain families of convex cones in R ⁿ .The purpose is to use known properties of convex cones in order to solve Helly type problems for convex sets in R ⁿ or for spherically convex sets in S _n , the n-dimensional unit sphere. These results are strongly related to Gale diagrams.     

Central and parallel projections of polytopes

Using the technique of Gale diagrams we give a characterization of point sets in (k - 1)-dimensional Eucliidean space that are obtained by projection of the vertex set of a convex k-polytope of given combinatorial type. This result is also a first step in finding an intrinsic geometric criterion to detect incorrect plane diagrams of 3-dimensional polyhedra.     

Subdifferentials of a minimum time function in Banach spaces

In general Banach space setting, we study the minimum time function determined by a closed convex set K and a closed set S (this function is simply the usual Minkowski function of K if S is the singleton consisting of the origin). In particular we show that various subdifferentials of a minimum time function are representable by virtue of corresponding normal cones of sublevel sets of the function.     

Necessary and sufficient conditions for the validity of Jensen’s inequality

We consider the d-dimensional Jensen inequality $$ T[\varphi(f_1, \dots, f_d)]\, \ge \, \varphi(T[f_1], \dots, T[f_d])\quad\quad(\ast)$$ T [ φ ( f 1 , … , f d ) ] ≥ φ ( T [ f 1 ] , … , T [ f d ] ) ( * ) as it was established by McShane in 1937r. Here T is a functional, φ is a convex function defined on a closed convex set ${K\subset \mathbb{R}^d}$ K ? R d , and f ₁, . . . , f _d are from some linear space of functions. Our aim is to find necessary and sufficient conditions for the validity of (*). In particular, we show that if we exclude three types of convex sets K, then Jensen’s inequality holds for a sublinear functional T if and only if T is linear, positive, and satisfies T[1] = 1. Furthermore, for each of the excluded types of convex sets, we present nonlinear, sublinear functionals T for which Jensen’s inequality holds. Thus the conditions on K are optimal. Our contributions generalize or complete several known results.     

Duality on locally convex cones

The theory of locally convex cones as a branch of functional analysis was presented by K. Keimel and W. Roth in [K. Keimel, W. Roth, Ordered Cones and Approximation, Lecture Notes in Math., vol. 1517, Springer-Verlag, Heidelberg, 1992]. We study some more results about dual cones and adjoint operators on locally convex cones. Moreover we introduce the concept of the uniformly precompact sets and discuss their relations with σ-bounded sets. Some results obtained about inductive limit, projective limit, metrizability and quotients of locally convex cones.     

Subdifferentials of a minimal time function in normed spaces

In a general normed vector space, we study the minimal time function determined by a differential inclusion where the set-valued mapping involved has constant values of a bounded closed convex set U and by a closed target set S. We show that proximal and Fréchet subdifferentials of a minimal time function are representable by virtue of corresponding normal cones of sublevel sets of the function and level or suplevel sets of the support function of U. The known results in the literature require the set U to have the origin as an interior point or U be compact. (In particular, if the set U is the unit closed ball, the results obtained reduce to the subdifferential of the distance function defined by S.)     

A complementarity partition theorem for multifold conic systems

Consider a homogeneous multifold convex conic system $$Ax = 0, \quad x\in K_1\times \cdots \times K_r$$ and its alternative system $$A^t y \in K_1^*\times \cdots \times K_r^*$$ , where K ₁,..., K _r are regular closed convex cones. We show that there is a canonical partition of the index set {1,...,r} determined by certain complementarity sets associated to the most interior solutions to the two systems. Our results are inspired by and extend the Goldman–Tucker Theorem for linear programming.     

Abstract Voronoi diagrams revisited

Abstract Voronoi diagrams [R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, vol. 400, Springer-Verlag, 1987] were designed as a unifying concept that should include as many concrete types of diagrams as possible. To ensure that abstract Voronoi diagrams, built from given sets of bisecting curves, are finite graphs, it was required that any two bisecting curves intersect only finitely often; this axiom was a cornerstone of the theory. In [A.G. Corbalan, M. Mazon, T. Recio, Geometry of bisectors for strictly convex distance functions, International Journal of Computational Geometry and Applications 6 (1) (1996) 45–58], Corbalan et al. gave an example of a smooth convex distance function whose bisectors have infinitely many intersections, so that it was not covered by the existing AVD theory. In this paper we give a new axiomatic foundation of abstract Voronoi diagrams that works without the finite intersection property.     

Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set?s chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

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.     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

Reprint of: Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.