On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

On the X-Y convex hull of a set of X-Y polygons

We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.     

On the convex hull of uniform random points in a simpled-polytope

Denote the expected number of facets and vertices and the expected volume of the convex hullP _n ofn random points, selected independently and uniformly from the interior of a simpled-polytope byE _n (f), E _n (v), andE _n (V), respectively. In this note we determine the sharp constants of the asymptotic expansion ofE _n (f), E _n (v), andE _n (V), asn tends to infinity. Further, some results concerning the expected shape ofP _n are given. The work of F. Affentranger was supported by the Swiss National Foundation.     

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     

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.

     

On the shape of the convex hull of random points

Summary Denote by E _n the convex hull of n points chosen uniformly and independently from the d-dimensional ball. Let Prob(d, n) denote the probability that E _n has exactly n vertices. It is proved here that Prob(d, 2 ^d/2 d ^-)1 and Prob(d, 2 ^d/2 d ^(3/4)+)0 for every fixed >0 when d. The question whether E _n is a k-neighbourly polytope is also investigated.     

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.     

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.     

Method of orienting curves for determining the convex hull of a finite set of points in the plane

In this article, we present an efficient algorithm to determine the convex hull of a finite planar set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Lösung einer regulären Aufgabenklasse der optimalen Steuerung in Großen mittels Orientierungskurven, Optimization, 18 (1987), pp. 65–81, for solving optimal control problems with state constraints). The convex hull is determined by parts of orienting lines and a final line. Two advantages of this algorithm over some variations of Graham's convex hull algorithm are presented.     

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.     

Distribution-independent properties of the convex hull of random points

Denote byV _n ^(d) the expected volume of the convex hull ofn points chosen independently according to a given probability measure in Euclideand-spaceE ^d. Ifd=2 ord=3 and is the measure corresponding to the uniform distribution on a convex body inE ^d, Affentranger and Badertscher derived that

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

On a conjecture of R. E. Miles about the convex hull of random points

Denoty byp _d+i (B _d ,d+m) the probability that the convex hull ofd+m points chosen independently and uniformly from ad-dimensional ballB _d possessesd+i(i=1,...,m) vertices. We prove Mile's conjecture that, given any integerm, p _d+m (B _d ,d+m)»1 asd». This is obvious form=1 and was shown by Kingman form=2 and by Miles form=3. Further, a related result by Miles is generalized, and several consequences are deduced.Dedicated to Professor E. Halwaka on the occasion of his seventieth     

On the complexity of finding first-order critical points in constrained nonlinear optimization

The complexity of finding $\epsilon $ -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $O(\epsilon ^{-2})$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.     

Extreme points of the closed convex hull of composition operators

We study the extreme points of the closed convex hull of the set of all composition operators on the space of bounded analytic functions and the disk algebra.     

On the complexity of some Euclidean problems of partitioning a finite set of points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

The order of points on the second convex hull of a simple polygon

Given a setV of points on the plane, if {q ₁,...,q _n } is the set of points on the second convex hull ofV, the order in which these points are visited in anyV-gon is characterized. This order must verify two similar conditions to those of Kuratowski's theorem for planar graphs. Moreover, the number of possible orders that verify these conditions is obtained. It isO(5 ⁿ ).