Applications of a semi-dynamic convex hull algorithm

We obtain new results for manipulating and searching semi-dynamic planar convex hulls (subject to deletions only), and apply them to derive improved bounds for two problems in geometry and scheduling. The new convex hull results are logarithmic time bounds for set splitting and for finding a tangent when the two convex hulls are not linearly separated. Using these results, we solve the following two problems optimally inO(n logn) time: (1) [matching] givenn red points andn blue points in the plane, find a matching of red and blue points (by line segments) in which no two edges cross, and (2) [scheduling] givenn jobs with due dates, linear penalties for late completion, and a single machine on which to process them, find a schedule of jobs that minimizes the maximum penalty.     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.     

Finding the convex hull of a simple polygon

It is well known that the convex hull of a set of n points in the plane can be found by an algorithm having worst-case complexity O(n log n). A short linear-time algorithm for finding the convex hull when the points form the (ordered) vertices of a simple (i.e., non-self-intersecting) polygon is given.     

A sublogarithmic convex hull algorithm

We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn ^1/3 divide-and-conquer and uses a simple pointer-based data structure.Part of this work was done when the last three authors were at the Department of Computer and Information Science, Linköping University. The research of the second author was supported by the Academy of Finland.     

One approach to constructing a minimal convex hull

The minimal convex hull of a subset of finite-dimensional space is constructed in a discrete fashion: at each step, we construct a new set that includes the inherited set. The procedure for finding the chain of sets involves geometrically evident constructions. This chain becomes stationary; i.e., from some number onward, all the sets of the chain being constructed coincide with the minimal convex hull. Our approach uses the principal result (Caratheodory’s theorem) underlying the conventional approach to constructing a minimal convex hull.     

On convex hull of Gaussian samples

Let X _i = {X _i (t), t ∈ T} be i.i.d. copies of a centered Gaussian process X = {X(t), t ∈ T} with values in\( {\mathbb{R}^d} \) defined on a separable metric space T. It is supposed that X is bounded. We consider the asymptotic behavior of convex hulls

$ {W_n} = {\text{conv}}\left\{ {{X_1}(t), \ldots, {X_n}(t),\,\,t \in T} \right\} $

and show that, with probability 1,

$ \mathop {{\lim }}\limits_{n \to \infty } \frac{1}{{\sqrt {{2\ln n}} }}{W_n} = W $

(in the sense of Hausdorff distance), where the limit shape W is defined by the covariance structure of X: W = conv{K _t , t ∈ T}, Kt being the concentration ellipsoid of X(t). We also study the asymptotic behavior of the mathematical expectations E f(W _n ), where f is an homogeneous functional.

     

The expected convex hull trimmed regions of a sample

Given a data set in the multivariate Euclidean space, we study regions of central points built by averaging all their subsets with a fixed number of elements. The averaging of these sets is performed by appropriately scaling the Minkowski or elementwise summation of their convex hulls. The volume of such central regions is proposed as a multivariate scatter estimate and a circular sequence algorithm to compute the central regions of a bivariate data set is described. Extended version of the conference paper Cascos (2006) presented at the 17th Conference of the European Regional Section of the International Association for Statistical Computing (COMPSTAT 2006, Rome, Italy, August 28–September 1, 2006). Supported by the Spanish Ministry of Education and Science under grant MTM2005-02254.     

Quadratic problems defined on a convex hull of points

In this paper we consider an algorithm for a class of quadratic problems defined on a polytope which is described as the convex hull of a set of points. The algorithm is based on simplex partitions using convex underestimating functions.     

On the area and perimeter of a random convex hull in a bounded convex set

Suppose K is a compact convex set in ℝ² and X _i , 1≤i≤n, is a random sample of points in the interior of K. Under general assumptions on K and the distribution of the X _i we study the asymptotic properties of certain statistics of the convex hull of the sample. Received: 24 July 1996/Revised version: 24 February 1998     

On the volume of the convex hull of two convex bodies

In this note we examine the volume of the convex hull of two congruent copies of a convex body in Euclidean $n$ -space, under some subsets of the isometry group of the space. We prove inequalities for this volume if the two bodies are translates, or reflected copies of each other about a common point or a hyperplane containing it. In particular, we give a proof of a related conjecture of Rogers and Shephard.     

The convex hull of the lattice points inside a curve

Let $C$ be a smooth convex closed plane curve. The $C$ -ovals $C(R,u,v)$ are formed by expanding by a factor  $R$ , then translating by  $(u,v)$ . The number of vertices $V(R,u,v)$ of the convex hull of the integer points within or on  $C(R,u,v)$ has order  $R^{2/3}$ (Balog and Bárány) and has average size $BR^{2/3}$ as $R$ varies (Balog and Deshouillers). We find the space average of  $V(R,u,v)$ over vectors  $(u,v)$ to be  $BR^{2/3}$ with an explicit coefficient  $B$ , and show that the average over  $R$ has the same  $B$ . The proof involves counting edges and finding the domain $D(q,a)$ of an integer vector, the set of  $(u,v)$ for which the convex hull has a directed edge parallel to  $(q,a)$ . The resulting sum over bases of the integer lattice is approximated by a triple integral.     

Some results on the convex hull of finitely many convex sets

A better than quadratic estimate is given for the volume of the convex hull of points on Hadamard manifolds with pinched curvature. It was known previously that the volume is bounded by some polynomial in . The estimate comes from the study of the convex hull of finitely many convex sets on Hadamard manifolds.

     

Some performance tests of convex hull algorithms

The two-dimensional convex hull algorithms of Graham, Jarvis, Eddy, and Akl and Toussaint are tested on four different planar point distributions. Some modifications are discussed for both the Graham and Jarvis algorithms. Timings taken of FORTRAN implementations indicate that the Eddy and Akl-Toussaint algorithms are superior on uniform distributions of points in the plane. The Graham algorithm outperforms the others on those distributions where most of the points are on or near the boundary of the hull.     

The convex hull of antichains in posets

Extending a result of Kleitman et al. [7] it is shown that the vertices on the convex hull off-vectors of all antichains of a poset come from antichains which are the unions of full orbits of the automorphism group.