The probability thatn random points in a triangle are in convex position

We show thatn random points chosen independently and uniformly from a triangle are in convex position with probability $$\frac{{2^n (3n - 3)!}}{{((n - 1)!)^3 (2n)!}}$$ .     

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

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

On the stretch factor of Delaunay triangulations of points in convex position

Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance |pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33.     

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

Lattice points in large convex bodies

In this article we investigate the numberA(t) of lattice points in B whereB is a convex body in ^s (s3) which has a smooth boundary with nonzero Gaussian curvature throughout, andt is a large real parameter. We establish an asymptotic formulaA(t)=Vt ^s/2+O(t ^(s)) (V the volume ofB) which improves upon a classic result ofE. Hlawka [5].To Professor Edmund Hlawka on his 75^th birthdayThis article was written while the first named author was visiting professor at Vienna University, in spring semester 1991.This paper is part of a research project supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung (Nr. P7514-PHY).     

Probability dominance in random outcomes

An intuitively appealing probability dominance relation for random outcomes is defined and investigated. Its properties, strengths, and weaknesses relative to stochastic dominance and meanvariance dominance are studied. It is shown that the proposed probability dominance complements existing solution concepts and strengthens one's confidence in decision making under uncertainty. Fundamental characteristics of nondominated random payoffs and methods for identifying them, for both general and specific classes, are reported. Application pitfalls and possible extensions are also discussed.     

Integral points on convex curves

The Ramanujan Journal - We estimate the maximal number of integral points which can be on a convex arc in $${mathbb {R}}^2$$ with given length, minimal radius of curvature and initial slope.     

Contact points of convex bodies

LetB be a convex body in ? ⁿ and let ? be an ellipsoid of minimal volume containingB. By contact points ofB we mean the points of the intersection between the boundaries ofB and ?. By a result of P. Gruber, a generic convex body in ? ⁿ has (n+3)·n/2 contact points. We prove that for every ?>0 and for every convex bodyB ? ? ⁿ there exists a convex bodyK having $$m \leqslant C(\varepsilon ) \cdot n\log ^3 n$$ contact points whose Banach-Mazur distance toB is less than 1+?. We prove also that for everyt>1 there exists a convex symmetric body Γ ? ? ⁿ so that every convex bodyD ? ? ⁿ whose Banach-Mazur distance to Γ is less thant has at least (1+c ₀/t ²)·n contact points for some absolute constantc ₀. We apply these results to obtain new factorizations of Dvoretzky-Rogers type and to estimate the size of almost orthogonal submatrices of an orthogonal matrix.     

A convex sets in general position

The notion of convex cones in general position has turned out to be useful in convex programming theory. In this paper we extend the notion to convex sets and give some characterizations which yield a better insight into this concept. We also consider the case of convex sets in S-general position.     

Connectedness of efficient points in convex and convex transformable vector optimization

Given a convex vector optimization problem with respect to a closed ordering cone, we show the connectedness of the efficient and properly efficient sets. The Arrow–Barankin–Blackwell theorem is generalized to nonconvex vector optimization problems, and the connectedness results are extended to convex transformable vector optimization problems. In particular, we show the connectedness of the efficient set if the target function f is continuously transformable, and of the properly efficient set if f is differentiably transformable. Moreover, we show the connectedness of the efficient and properly efficient sets for quadratic quasiconvex multicriteria optimization problems.     

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