Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

Limit theorems for convex hulls

It is shown that the process of vertices of the convex hull of a uniform sample from the interior of a convex polygon converges locally, after rescaling, to a strongly mixing Markov process, as the sample size tends to infinity. The structure of the limiting Markov process is determined explicitly, and from this a central limit theorem for the number of vertices of the convex hull is derived. Similar results are given for uniform samples from the unit disk.     

Output-sensitive results on convex hulls,extreme points,and related problems

We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems. We show that thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in time; this is optimal if for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n ^2−γ) time for any constant . Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms the input is assumed to be in general position. This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.     

Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points

Summary. A general formula is proved, which relates the equiaffine inner parallel curves of a plane convex body and the probability that the convex hull of j independent random points is disjoint from the convex hull of k further independent random points. This formula is applied to improve some well-known results in geometric probability. For example, an estimate, which was established for a special case by L. C. G. Rogers, is obtained with the best possible bound, and an asymptotic formula due to A. Rényi and R.␣Sulanke is extended to an asymptotic expansion. Received: 21 May 1996     

Evaluating inclusion functionals for random convex hulls

Summary The inclusion functional of a random convex set, evaluated at a fixed convex set K, measures the probability that the random convex set contains K. This functional is an analogue of the complement of the distribution function of an ordinary random variable. A methodology is described for evaluating the inclusion functional for the case where the random convex set is generated as the convex hull of n i.i.d. points from a distribution function F in the plane. For general K and F, the inclusion probability is difficult to compute in closed form. The case where K is a straight line segment is examined in detail and, in this situation, a simple answer is given for an interesting class of distributions F.     

Limit theorems for functionals of convex hulls

Summary In [4] a central limit theorem for the number of vertices of the convex hull of a uniform sample from the interior of a convex polygon is derived. This is done by approximating the process of vertices of the convex hull by the process of extreme points of a Poisson point process and by considering the latter process of extreme points as a Markov process (for a particular parametrization). We show that this method can also be applied to derive limit theorems for the boundary length and for the area of the convex hull. This extents results of Rényi and Sulanke (1963) and Buchta (1984), and shows that the boundary length and the area have a strikingly different probabilistic behavior.     

逼近一致凸Banach空间中渐近非扩张映象的不动点

借助于B ruck′s不等式,研究了一致凸Banach空间中渐近非扩张映象不动点的具误差的Ish ikaw a迭代序列的强收敛定理.所得的结果推广和改进了Schu,Rhoades,周海云,王绍荣等作者的相应结果.     

Metric entropy of convex hulls

LetT be a precompact subset of a Hilbert space. The metric entropy of the convex hull ofT is estimated in terms of the metric entropy ofT, when the latter is of order ε^ℒ2. The estimate is best possible. Thus, it answers a question left open in [CKP].     

A constant-time parallel algorithm for computing convex hulls

The convex hull of a finite set of points in the plane can be computed in constant time using a polynomial number of processors.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC - A3336.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Canonical models for a class of polynomially convex hulls

We use holomorphic motions and Beltrami equation to study a class of polynomially convex hulls in ℂ ² with Jordan fibers over the disc D. It is shown that every such hull is biholomorphically equivalent to a unique (up to suitable normalisation) canonical model. These models are the hulls whose complements in D×ℂmacr; are biholomorphic to a bidisc and are further characterized in terms of capacity of the fibers, Green’s function, pseudoconcavity and approximability by (very) special analytic polyhedra. Received: 11 September 1995 / Revised version: 11 March 1996