Approximating largest convex hulls for imprecise points

Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.     

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.     

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     

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].     

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.     

Interior points of the convex hull of few points in\mathbb{E}^d

We show that ifP , |P|=d+k,dk1 andO int convP, then there exists a simplexS of dimension with vertices inP, satisfyingO rel intS, the bound being sharp. We give an upper bound for the minimal number of vertices of facets of a (j-1)-neighbourly convex polytope in withv vertices.Research (partially) supported by Hung. Nat. Found. for Sci. Research, grant no. 1817Research (partially) supported by Hung. Nat. Found. for Sci. Research, grant no. 326-0213     

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).     

The Bourgain property and convex hulls

Let (Ω, Σ, μ) be a complete probability space and let X be a Banach space. We consider the following problem: Given a function f: Ω → X for which there is a norming set B ? B_{X *} such that Z_f,B = {x * ○ f: x * ∈ B } is uniformly integrable and has the Bourgain property, does it follow that f is Birkhoff integrable? It turns out that this question is equivalent to the following one: Given a pointwise bounded family ?? ? ?^Ω with the Bourgain property, does its convex hull co(??) have the Bourgain property? With the help of an example of D. H. Fremlin, we make clear that both questions have negative answer in general. We prove that a function f: Ω → X is scalarly measurable provided that there is a norming set B ? B_{X *} such that Z_f,B has the Bourgain property. As an application we show that the first problem has positive solution in several cases, for instance: (i) when B_{X *} is weak* separable; (ii) under Martin's axiom, for functions defined on [0, 1] with values in a Banach space with density character smaller than the continuum. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Near optimal minimal convex hulls of disks

Journal of Global Optimization - The minimal convex hulls of disks problem is to find such arrangements of circular disks in the plane that minimize the length of the convex hull boundary. The...