Search

Given two convex d-polytopes P and Q in R d for d ⩾ 3 , we study the problem of bundling P and Q in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing P and a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d ⩾ 3 . The running time is O ( n ( d − 1 ) ⌊ d + 1 2 ⌋ ) , where n denotes the number of vertices of P and Q. In particular, in dimension d = 3 , our algorithm runs in O ( n 4 ) time. We also give an example of polytopes P and Q such that in the smallest container the translates of P and Q do not touch.

In this chapter, we give some definitions and results connected with convex analysis, convex programming, and Lagrangian duality. In Part Two, these concepts and results are utilized in developing suitable optimality conditions and numerical methods for solving some convex problems.

In this article, we extend the definition of γ-active constraints for linear semi-infinite programming to a definition applicable to convex semi-infinite programming, by two approaches. The first approach entails the use of the subdifferentials of the convex constraints at a point, while the second approach is based on the linearization of the convex inequality system by means of the convex conjugates of the defining functions. By both these methods, we manage to extend the results on γ-active constraints from the linear case to the convex case.

In this paper we propose a new approach of the compressive sensing (CS) reconstruction problem based on a geometrical interpretation of l 1 -norm minimization. By taking a large l 1 -norm value at the initial step, the intersection of l 1 -norm and the constraint curves forms a convex polytope and by exploiting the fact that any convex combination of the polytope’s vertexes gives a new point that has a smaller l 1 -norm, we are able to derive a new algorithm to solve the CS reconstruction problem. Compared to the greedy algorithm, this algorithm has better performance, especially in highly coherent environments. Compared to the convex optimization, the proposed algorithm has simpler computation requirements. We tested the capability of this algorithm in reconstructing a randomly down-sampled version of the Dow Jones Industrial Average (DJIA) index. The proposed algorithm achieved a good result but only works on real-valued signals.

Reducing samples through convex hull vertices selection (CHVS) within each class is an important and effective method for online classification problems, since the classifier can be trained rapidly with the selected samples. However, the process of CHVS is NP-hard. In this paper, we propose a fast algorithm to select the convex hull vertices, based on the convex hull decomposition and the property of projection. In the proposed algorithm, the quadratic minimization problem of computing the distance between a point and a convex hull is converted into a linear equation problem with a low computational complexity. When the data dimension is high, an approximate, instead of exact, convex hull is allowed to be selected by setting an appropriate termination condition in order to delete more nonimportant samples. In addition, the impact of outliers is also considered, and the proposed algorithm is improved by deleting the outliers in the initial procedure. Furthermore, a dimension convention technique via the kernel trick is used to deal with nonlinearly separable problems. An upper bound is theoretically proved for the difference between the support vector machines based on the approximate convex hull vertices selected and all the training samples. Experimental results on both synthetic and real data sets show the effectiveness and validity of the proposed algorithm.

A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a spherical surface and a convex compact set is proposed. The idea behind the algorithm is to reduce the original minimization problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.

A complete, elementary analysis is presented for second-order difference equations xn=g(xn-1,xn-2) where g is strictly monotone and convex in the first quadrant. It is shown that the dynamics of any such equation partitions the phase space into two basins of attraction, one of which is bounded and convex (possibly empty). In the case of two non-empty basins, each point on their common boundary corresponds to an asymptotically 2-periodic solution. The results and examples presented complement previous studies of second-order equations in the literature.

The general notion of convexity also applies to a graph G = ( V , E ) . A subset V c of V is called a convex set if all shortest paths with end vertices in V c remain within V c . A convex cut of G is a partition ( V 1 , V 2 ) of V such that V 1 and V 2 are convex sets (halfspaces). Finding convex cuts is NP -hard for general graphs. In this paper we first characterize the convex cuts of a connected bipartite graph G ′ in terms of the Djokovic relation, a reflexive and symmetric relation on the edges of a graph that is based on shortest paths between the edges' end vertices. Specifically, we show that a cut of G ′ is convex if and only if the Djokovic relation holds for any pair of edges in its cut-set. As a consequence, all convex cuts of G ′ = { V ′ , E ′ } can be found in O ( | V ′ | | E ′ | ) . We then characterize the convex cuts of a general connected graph G using the Djokovic–Winkler relation θ and another relation τ on the edges of G. Based on this general characterization, we show how one can find all convex cuts of G in polynomial time. The key parts here are (i) describing the Djokovic–Winkler relation on the edges of G in terms of the Djokovic relation θ ′ on the bipartite graph obtained from G by subdividing each edge of G into two edges, (ii) studying the interplay of θ ′ and τ on plane curves representing convex cuts, and (iii) a running time analysis of our algorithm for finding the convex cuts. Our method for characterizing and finding convex cuts of a connected plane graph G is motivated by the concept of alternating cuts and conditions on the latter to be convex. In the last part of this paper we represent alternating cuts as plane curves and focus on their intersection pattern. If the plane curves form an arrangement of pseudolines, G is scale embedded in its dual, and any edge of G is contained in the cut-set of a convex cut of G.

The family ${\mathcal{F}}_{\unicode[STIX]{x1D706}}$ of orientation-preserving harmonic functions $f=h+\overline{g}$ in the unit disc $\mathbb{D}$ (normalised in the standard way) satisfying $$\begin{eqnarray}h^{\prime }(z)+g^{\prime }(z)=\frac{1}{(1+\unicode[STIX]{x1D706}z)(1+\overline{\unicode[STIX]{x1D706}}z)},\quad z\in \mathbb{D},\end{eqnarray}$$ for some $\unicode[STIX]{x1D706}\in \unicode[STIX]{x2202}\mathbb{D}$, along with their rotations, play an important role among those functions that are harmonic and orientation-preserving and map the unit disc onto a convex domain. The main theorem in this paper generalises results in recent literature by showing that convex combinations of functions in ${\mathcal{F}}_{\unicode[STIX]{x1D706}}$ are convex.

Choose uniform random points $$X_1, \dots , X_n$$ in a given convex set and let $${\text { conv}}[X_1, \dots , X_n]$$ be their convex hull. It is shown that in dimension three the expected volume of this convex hull is in general not monotone with respect to set inclusion. This answers a question by Meckes in the negative. The given counterexample is formed by uniformly distributed points in the three-dimensional tetrahedron together with a small perturbation of it. As side result we obtain an explicit formula for all even moments of the volume of a random simplex which is the convex hull of three uniform random points in the tetrahedron and the center of one facet.

In this paper, using Riemann-Liouville integral operators, we establish new fractional in- tegral inequalities of Hermite-Hadamard-Fejer type for co-ordinated convex functions on a rectangle of R^2. The results presented here would provide extensions of those given in earlier works.

We establish unique existence of $p$-barycenter of any probability measure for $p \ge 2$ on CAT(1)-spaces of small radii. In our proof, we employ Kendall's convex function on a ball of CAT(1)-spaces instead of the convexity of distance function. Various properties of $p$-barycenter on those spaces are also presented. They extend the author's previous work [Yo].

Recently, A. Greco utilized convex rearrangements to present some new and interesting existence results for noncoercive functionals in the calculus of variations. Moreover, the integrands were not necessarily convex. In particular, using convex rearrangements permitted him to establish the existence of convex minimizers essentially considering the uniform convergence of the minimizing sequence of trajectories and the pointwise convergence of their derivatives. The desired lower semicontinuity property is now a consequence of Fatou's lemma. In this paper we point out that such an approach was considered in the late 1930's in a series of papers by E.J. McShane for problems satisfying the usual coercivity condition. In addition, we will update some hypotheses that McShane made by making use of a result due to T.S. Angell, concerning property (D) on the avoidance of the Lavrentiev phenomenon.

Agraïments: The first and third authors are partially supported by FAPEMIG grant APQ-001082/14. The third author is partially supported by CNPq grant 472321/2013-7 and by FAPEMIG grant PPM-00516-15. The second and third autors are supported by CAPES CSF-PVE grant 88881.030454/2013-01. MacMillan and Bartky in 1932 proved that there is a unique isosceles trapezoid central configuration of the 4--body problem when two pairs of equal masses are located at adjacent vertices. After this result the following conjecture was well known between people working on central configurations: The isosceles trapezoid is the unique convex central configuration of the planar 4--body problem when two pairs of equal masses are located at adjacent vertices. We prove this conjecture.

The aim of this paper is to obtain some new bounds having Riemann type quantum integrals within the class of strongly convex functions. The results obtained are sharp on limit q → 1. These new results reduce to Tariboon-Ntouyas, Merentes-Nikodem and other previously known results when q → 1, where 0 < q < 1. The sharpness of the results of Tariboon-Ntouyas and Merentes-Nikodem is proved as a consequence.

Central configurations of the n-body problem have been studied for more than 200 years since the pioneer works of Euler and Lagrange. In this article we study convex central configurations which are not strictly convex. We give explicit examples of such configurations in both planar and spatial n-body problems. Particularly, in the spatial case, we consider regular polyhedra with bodies of same mass m at the vertices and bodies of same mass M at the middle points of each edge. In this setting we prove that the cube is the unique regular polyhedron such that this construction leads to a convex central configuration which is not strictly convex.

For a finite/infinite family of closed convex sets with nonempty intersection in Hilbert space, we consider the (bounded) linear regularity property and the linear convergence property of the projection-based methods for solving the convex feasibility problem. Several sufficient conditions are provided to ensure the bounded linear regularity in terms of the interior-point conditions and some finite codimension assumptions. A unified projection method, called Algorithm B-EMOPP, for solving the convex feasibility problem is proposed, and by using the bounded linear regularity, the linear convergence results for this method are established under a new control strategy introduced here.

Invertibility of all convex combinations of A and I is equivalent to the real eigenvalues of A, if any, being positive. Invertibility of all matrices whose rows are convex combinations of the respective rows of A and I is equivalent to A having positive principal minors (i.e. being a P-matrix). These results are extended by considering convex combinations of higher powers of A and of their rows. The invertibility of matrices in these convex hulls is associated with the eigenvalues of A lying in open sectors of the right-half plane and provides a general context for the theory of matrices with P-matrix powers.

We investigate the bend-minimization problem with respect to a new drawing style called an orthogonally convex drawing, which is an orthogonal drawing with an additional requirement that each inner face is drawn as an orthogonally convex polygon. For the class of biconnected plane graphs of maximum degree 3, we present a necessary and sufficient condition for the existence of a no-bend orthogonally convex drawing, which in turn, enables a linear time algorithm to check and construct such a drawing if one exists. We also develop a flow network formulation for bend-minimization in orthogonally convex drawings, yielding a polynomial time solution for the problem. An interesting application of our orthogonally convex drawing technique is to characterize internally triangulated plane graphs that admit floorplans using only orthogonally convex modules subject to given orthogonally convex boundary constraints.

Radii of convexity, starlikeness, lemniscate starlikeness and close-to-convexity are determined for the convex combination of the identity map and a normalized convex functionFgiven byf(z) =α z+(1−α)F(z).

Designing an algorithm to deal with a convex shape is easier than that for a concave shape. Efficient algorithms are required to process concave shapes, because every application does not deal with convex shapes. An alternative approach is to first transform a concave shape into a set of convex shapes so that efficient algorithms available for convex shapes can be utilized. This paper proposes an algorithm for partitioning a concave polygon into smaller number of convex pieces. Each resultant convex piece then can be processed using a simple algorithm applicable to convex shapes. In this way, any arbitrary shape can be processed using such simple algorithms with the aid of the proposed algorithm. There are plenty of algorithms available in literature to solve convex partitioning problem. Hertel Mehlhorn algorithm is the most efficient algorithm, but it does not minimize the number of convex pieces satisfactorily. Further the Hertel Mehlhorn algorithm is the minimum memory consuming algorithm available in literature. Later Geene proposed an algorithm which gives the minimum number of convex pieces. It uses dynamic programming technique and needs high amount of memory. Therefore Geene’s algorithm is not suitable for systems where the memory is limited. Chazelle proposed an efficient algorithm which gives minimum number of convex pieces. However a data structure to implement Chazelle’s algorithm is not available in literature. The experimental results showed that the proposed algorithm gives smaller number of convex pieces than the Hertel Mehlhorn algorithm. The memory consumption of the proposed algorithm is also lower than the Hertel Mehlhorn algorithm.

In this paper, we prove Sherman like inequalities for convex sequences and nondecreasing convex functions. Thus we develop some results by S. Wu and L. Debnath [19]. In consequence, we derive discrete versions for convex sequences of Petrovic and Giaccardi?s inequalities. As applications, we establish some generalizatons of Fej?r inequality for convex sequences. We also study inequalities of Hermite-Hadamard type. Thus we extend some recent results of Latreuch and Bela?di [8]. In our considerations we use some matrix methods based on column stochastic and doubly stochastic matrices.

The convex hull of a set of points, $C$, serves to expose extremal properties of $C$ and can help identify elements in $C$ of high interest. For many problems, particularly in the presence of noise, the true vertex set (and facets) may be difficult to determine. One solution is to expand the list of high interest candidates to points lying near the boundary of the convex hull. We propose a quadratic program for the purpose of stratifying points in a data cloud based on proximity to the boundary of the convex hull. For each data point, a quadratic program is solved to determine an associated weight vector. We show that the weight vector encodes geometric information concerning the point's relationship to the boundary of the convex hull. The computation of the weight vectors can be carried out in parallel, and for a fixed number of points and fixed neighborhood size, the overall computational complexity of the algorithm grows linearly with dimension. As a consequence, meaningful computations can be complete...

We show that the maximum total perimeter ofk plane convex bodies with disjoint interiors lying inside a given convex body C is equal to $\operatorname{per}\, (C)+2(k-1)\operatorname{diam}\, (C)$ , in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body.

In this paper, by using Wu–Debnath’s method, we establish inequalities of Hammer–Bullen type for convex sequences and nondecreasing convex functions. In particular, we give an extension of a recent Farissi’s inequality. By assuming the symmetry of an involved sequence, we derive an inequality of Fejer–Hammer–Bullen type for convex sequences. In addition, we establish some companions of an Hermite–Hadamard like inequality by Latreuch and Belaidi. In our approach we use matrix methods based on column stochastic matrices.

A convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice $\Omega(\eta)$, that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex sets., Comment: 25 pages, 1 figure, submitted

We describe a general result which ensures counter-examples for certain problems of unique determination for convex bodies. Using this result, we show a convex body K ⊂ R n is not uniquely determined by its convex intersection body C I ( K ) , introduced by Meyer and Reisner in 2011.

To solve the problem of rigid/non-rigid 3D point set registration, a novel convex hull indexed Gaussian mixture model (CH-GMM) is proposed in this paper. The model works by computing a weighted Gaussian mixture model (GMM) response over the convex hull of each point set. Three conditions, proximity, area conservation and projection consistency, are incorporated into the model so as to improve its performance. Given that the convex hull is the tightest convex set of a point set, the combination of Gaussian mixture and convex hull can effectively preserve the topological structure of a point set. Furthermore, computational complexity can be significantly reduced since only the GMM of the convex hull (instead of the whole point set) needs to be calculated. Rigid registration is achieved by seeking the best rigid transformation parameters yielding the most similar CH-GMM responses. Non-rigid deformation is realized by optimizing the coordinates of the control points used by the thin-plate spline model for interpolating the entire point set. Experiments are designed to evaluate a method's robustness to rotational changes between two point sets, positional noise, differences in density and partial overlap. The results demonstrated better robustness and registration accuracy of CH-GMM based method over state-of-the-art methods including iterative closest point, coherent point drift and the GMM method. Besides, the computation of CH-GMM is efficient. A novel CH-GMM method is proposed for non-rigid registration of point sets.The CH-GMM can effectively present the topological information of point set.The CH-GMM matching of the point sets is very fast.The registration is very robust for points with large differences.

Despite the significant attention they have drawn, big-bucket lot-sizing problems remain notoriously difficult to solve. Previous literature contained results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multiperiod submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation. We propose a methodology that can approximate the convex hulls of all such possible relaxations by generating violated valid inequalities. To generate such inequalities, we separate two-period projections of fractional linear programming solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation and can therefore be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.

Some Hermite-Hadamard type inequalities involving fractional integrals for m-convex and (α,m)-convex functions are obtained.

A graph has strong convex dimension $2$, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension $2$ are planar and therefore have at most $3n-6$ edges. We prove that all such graphs have at most $2n-3$ edges while on the other hand we present a class of non-planar graphs of strong convex dimension $2$. We also give lower bounds on the maximum number of edges a graph of strong convex dimension $2$ can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years., Comment: 15 pages, 12 figures, improved exposition

Decomposing a 3D model into approximately convex components has gained more attention recently due to its ability to efficiently generate small decompositions with controllable concavity bounds. However, current methods are computationally expensive and require many user parameters. These parameters are usually unintuitive thus adding unnecessary obstacles in processing a large number of meshes with various types and shapes or meshes that are generated online within applications such as video games. In this paper, we investigate an approach that decomposes a mesh P based on the identification of convex ridges. Intuitively, convex ridges are the protruding parts of the mesh P . Our method, called CoRiSe, extracts nearly convex components of P by separating each convex ridge from all the other convex ridges through the new concept of residual concavity. CoRiSe źtakes a single user parameter: concavity tolerance which controls the maximum concavity of the final components, as input, along with other two fixed parameters for encoding the smoothness term of graph cut. We show that our method can generate comparable (sometimes noticeably better) segmentations in significant shorter time than the current state-of-art methods. Finally, we demonstrate applications of CoRiSe, including physically-based simulation, cage generation, model repair and mesh unfolding. A segmentation method produces meshes with bounded concavity.The method detects and separates protruding parts called convex ridges.The proposed method requires very few user parameters.The segmentation can be done faster than the existing approaches.Applications in simulation, deformation, mesh repair and unfolding are shown.

A conjecture appeared recently in Cacchiani etal. (2013) that a proposed LP relaxation of a certain integer programming problem defines the convex hull of its integer points. We review a little known technique described in Zuckerberg (2004) that can be used to construct geometric proofs that an LP relaxation is convex hull defining. In line with this technique, we show that their conjecture is correct.

In this paper, we consider a multi-agent convex optimization problem whose goal is to minimize a global convex objective function that is the sum of local convex objective functions, subject to global convex inequality constraints and several randomly occurring local convex state constraint sets. A distributed primal-dual random projection subgradient (DPDRPS) algorithm with diminishing stepsize using local communications and computations is proposed to solve such a problem. By employing iterative inequality techniques, the proposed DPDRPS algorithm is proved to be convergent almost surely. Finally, a numerical example is illustrated to show the effectiveness of the theoretical analysis.

Point set registration plays a crucial role in numerous computer vision applications. This paper proposes a novel and general approach called three-point convex hull matching (3PCHM) for registering two point sets with similarity transform. First, convex hulls are extracted from both point sets. Triangular patches on the surface of convex hulls are specified by predefining their normal vectors, thus guaranteeing that all points are located on the same side of any randomly selected triangle plane. Second, the potential similar triangle pair set is obtained by comparing the length ratio of the edges on the two extracted convex hulls. Thereafter, the transformation parameters for each pairwise triangle are calculated by minimizing the Euclidean distance between the corresponding vertex pairs. Furthermore, a k-dimensional (k-d) tree is used to accelerate the closest point search for the whole point sets. Third, outliers that may lead to significant errors are discarded by integrating the random sample consensus algorithm for global optimization. Experiments show that the proposed 3PCHM is robust even with the existence of noise and outliers and is effective in cases of part-to-part registration and part-to-whole registration.

International audience; In this paper we introduce a new estimator for the support of a multivariatedensity. It is defined as a union of convex hulls of observations contained in balls of fixed radius.We study the asymptotic behavior of this ``local convex hull" for the estimation of the support and its boundary.When the support is smooth enough, the proposed estimator is proved to be, eventually almost surely, homeomorphic to the support.Numerical simulations on both simulated and real data illustrate the performance of our estimator.

The problem of shadow is solved. It is equivalent to the problem of finding conditions for a point to belong to a generalized convex hull of a family of compact sets.

In order to express a polyhedron as the Minkowski sum of a polytope and a polyhedral cone, Motzkin (Beitrage zur Theorie der linearen Ungleichungen. Dissertation, University of Basel, 1936) devised a homogenization technique that translates the polyhedron to a polyhedral cone in one higher dimension. Refining his technique, we present a conical representation of a set in the Euclidean space. Then, we use this representation to reach four main results: First, we establish a convex programming based framework for determining a maximal element—an element with the maximum number of positive components—of a non-negative convex set—a convex set in the non-negative Euclidean orthant. Second, we develop a linear programming problem for finding a relative interior point of a polyhedron. Third, we propose two procedures for identifying a strictly complementary solution in linear programming. Finally, we generalize Motzkin’s (Beitrage zur Theorie der linearen Ungleichungen. Dissertation, University of Basel, 1936) representation theorem for a class of closed convex sets in the Euclidean space.

We characterize best approximations in L p ( 1 ≤ p ∞ ) from a class of convex subcones of the convex cone of nonnegative functions and the convex cone of increasing functions; in particular, from the convex cones themselves. These subcones arise naturally in applications of constrained or shape-preserving approximation.

A translation body of a convex body is the convex hull of two of its translates intersecting each other. In the 1950s, Rogers and Shephard found the extremal values, over the family of n-dimensional convex bodies, of the maximal volume of the translation bodies of a given convex body. In our paper, we introduce a normed version of this problem, and for the planar case, determine the corresponding quantities for the four types of volumes regularly used in the literature: Busemann, Holmes–Thompson, and Gromov’s mass and mass*. We examine the problem also for higher dimensions, and for centrally symmetric convex bodies.

Algorithm for computing the convex hull of a set of points in E3 we are proposed.The algorithm is based on spherical space subdivision.The algorithm eliminates as many input points as possible before the convex hull calculation.Experimental results show that the proposed algorithm achieves a better time complexity in comparison with other algorithms in E3. Convex hulls are fundamental geometric tools used in a number of algorithms. This paper presents a fast, simple to implement and robust Smart Convex Hull (S-CH) algorithm for computing the convex hull of a set of points in E3. This algorithm is based on "spherical" space subdivision. The main idea of the S-CH algorithm is to eliminate as many input points as possible before the convex hull construction. The experimental results show that only a very small number of points are used for the final convex hull calculation. Experiments made also proved that the proposed S-CH algorithm achieves a better time complexity in comparison with other algorithms in E3.

Two probability measures admit a martingale transition if and only if they are ordered in the convex order (Kellerer, 1972). We show that the commonly used quantization method, L 2 -quantization, does not have the property of preserving the convex order. We introduce an alternative quantization method and demonstrate that it preserves the convex order. This result has implications concerning the choice of quantization methods for the numerical construction of martingales with specified marginals.

A minimization problem with a convex separable objective function subject to linear equality constraints and box constraints (bounds on the variables) is considered. Necessary and sufficient optimality condition is proved for a feasible solution to be an optimal solution to this problem. Primal-dual analysis is also included. Examples of some convex separable objective functions for the considered problem are presented.