On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Delaunay triangulation and the convex hull ofn points in expected linear time

An algorithm is presented which produces a Delaunay triangulation ofn points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull ofn points in the Euclidean plane.     

Counting the onion

Iteratively computing and discarding a set of convex hulls creates a structure known as an “onion.” In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n^2/3). Additionally, we show that in general the bound is Θ(n^2/(d+1)) for points distributed in a d‐dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full‐dimensional shape with a nonempty interior. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

An efficient convex hull algorithm for finite point sets in 3D based on the Method of Orienting Curves

This article describes an efficient convex hull algorithm for finite point sets in 3D based on the idea of the Method of Orienting Curves (introduced by Phu in Optimization, 18 (1987) pp. 65–81, for solving optimal control problems with state constraints). The actual run times of our algorithm and known gift-wrapping algorithm on the set of random points (in uniform distribution) show that our algorithm runs significantly faster than the gift-wrapping one.     

Some properties of convex hulls generated by homogeneous Poisson point processes in an unbounded convex domain

LetC(A) be the convex hull generated by a Poisson point process in an unbounded convex setA. A representation ofAC(A) as the union of curvilinear triangles with independent areas is established. In the case whenA is a cone the properties of the representation are examined more completely. It is also indicated how to simulateC(A) directly without first simulating the process itself.     

On the performance of peeling algorithms

The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n^˙ Log (n)) execution time, may give an O(n^˙n^˙ Log (n)) to peel all the set; an O(n^˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n^˙n) performance.     

On Fuzzy Simplex and Fuzzy Convex Hull

In this paper,we discuss fuzzy simplex and fuzzy convex hull,and give several representation theorems for fuzzy simplex and fuzzy convex hull.In addition,by giving a new characterization theorem of fuzzy convex hull,we improve some known results about fuzzy convex hull.     

Mean convex hulls and least area disks spanning extreme curves

We show that for any extreme curve in a 3-manifold M, there exist a canonical mean convex hull containing all least area disks spanning the curve. Similar result is true for asymptotic case in such that for any asymptotic curve , there is a canonical mean convex hull containing all minimal planes spanning Γ. Applying this to quasi-Fuchsian manifolds, we show that for any quasi-Fuchsian manifold, there exist a canonical mean convex core capturing all essential minimal surfaces. On the other hand, we also show that for a generic C³-smooth curve in the boundary of C³-smooth mean convex domain in ℝ³, there exist a unique least area disk spanning the curve.     

Representation of Bounded Convex Sets By Rational Convex Hull Of Its Gamma-Extreme Points

H. Minkowski proved C= convext C whenever C is a compact convex subset of a finite-dimensional linear space. If C is bounded but not closed, this representation does not hold anymore. In this case, we introduce the set of so-called γ-extreme points extγC of C and show C = convext γ C = raco extγ C, where raco M denotes the rational convex hull of M.     

Concave functions,blaschke products,and polygonal mappings

We consider the class Co(p) of all conformal maps of the unit disk onto the exterior of a bounded convex set. We prove that the triangle mappings, i.e., the functions that map the unit disk onto the exterior of a triangle, are among the extreme points of the closed convex hull of Co(p). Moreover, we prove a conjecture on the closed convex hull of Co(p) for all p ∈ (0, 1) which had partially been proved by the authors for some values of p ∈ (0, 1).     

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.     

Sequential convexification in reverse convex and disjunctive programming

This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.The research underlying this report was supported by Grant ECS-8601660 of The National Science Foundation and Contract N00014-85-K-0198 with the Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.On leave from the University of Aarhus, Denmark.     

稀疏降维的近似凸壳覆盖一类分类器构造

针对高维数据集常常存在冗余和维数灾难,在其上直接构造覆盖模型难以充分反映数据分布信息的问题,提出一种基于稀疏降维近似凸壳覆盖模型.首先采用同伦算法求解稀疏表示中l_1优化问题,通过稀疏约束自动获取合理近邻数并构建图,再通过LPP(Locality Preserving Projections)来进行局部保持投影,进而实现对高维空间快速有效地降维,最后在低维空间通过构造近似凸壳覆盖实现一类分类.在UCI数据库,MNIST手写体数据库和MIT-CBCL人脸识别数据库上的实验结果证实了方法的有效性,与现有的一类分类算法相比,提出的覆盖模型具有更高的分类正确率.     

An Analog of the Krein--Mil'man Theorem for Strongly Convex Hulls in Hilbert Space

We prove the following theorem: in Hilbert space a closed bounded set is contained in the strongly convex R-hull of its R-strong extreme points. R-strong extreme points are a subset of the set of extreme points (it may happen that these two sets do not coincide); the strongly convex R-hull of a set contains the closure of the convex hull of the set.     

Convex hull theorem for multiply connected domains in the plane with an estimate of the quasiconformal constant

For any multiply connected domain Ω in R2, let S be the boundary of the convex hull in H3 of R2\Ω which faces Ω. Suppose in addition that there exists a lower bound l > 0 of the hyperbolic lengths of closed geodesics in Ω. Then there is always a K-quasiconformal mapping from S to Ω, which extends continuously to the identity on S = Ω, where K depends only on l. We also give a numerical estimate of K by using the parameter l.     

A Level Set Representation Method for N-Dimensional Convex Shape and Applications

In this work,we present a new method for convex shape representation,which is regardless of the dimension of the concerned objects,using level-set approaches.To the best of our knowledge,the proposed prior is the first one which can work for high dimensional objects.Convexity prior is very useful for object completion in computer vision.It is a very challenging task to represent high dimensional convex objects.In this paper,we first prove that the convexity of the considered object is equivalent to the convexity of the associated signed distance function.Then,the second order condition of convex functions is used to characterize the shape convexity equivalently.We apply this new method to two applications:object segmentation with convexity prior and convex hull problem(especially with outliers).For both applications,the involved problems can be written as a general optimization problem with three constraints.An algorithm based on the alternating direction method of multipliers is presented for the optimization problem.Numerical experiments are conducted to verify the effectiveness of the proposed representation method and algorithm.     

R~n中构形和单纯复形的一个最优度量不等式

对于R~n中一般位置的点构形,定义了第r个极小凸包距离的概念,证明了极小凸包距离和极小点-超平面距离之间的一个最优不等式.该不等式的一个直接推论是:对于R~n中一个k-维单纯复形K,我们能用其顶点集的极小点-超平面距离下估计K的Gromov-Guth厚度.进一步,在每一个维数k,构造了例子说明该下界几乎是最优的.     

Faster than the Fast Legendre Transform,the Linear-time Legendre Transform

A new algorithm to compute the Legendre–Fenchel transform is proposed and investigated. The so-called Linear-time Legendre Transform (LLT) improves all previously known Fast Legendre Transform algorithms by reducing their log-linear worst-case time complexity to linear. Since the algorithm amounts to computing several convex hulls and sorting, any convex hull algorithm well-suited for a particular problem gives a corresponding LLT algorithm. After justifying the convergence of the Discrete Legendre Transform to the Legendre–Fenchel transform, an extended computation time complexity analysis is given and confirmed by numerical tests. Finally, the LLT is illustrated with several examples and a LLT MATLAB package is described. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

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.