Home | Bookmarks | Papers | Blog |

In this paper we present several results on the expected complexity of a convex hull of

(i) We show that the expected
number of vertices of the convex hull of **n** points, chosen
uniformly and independently from a disk, is **O(n ^{1/3})**.
Applying the same technique to the case where the points are
chosen from a convex polygon with

(ii) Let **D** be a set of directions
in the plane, we define a generalized notion of convexity induced
by **D**, which extends both rectilinear convexity, and standard
convexity.

We prove that the expected complexity of the **D**-convex hull of
a set of **n** points, chosen uniformly and independently from a
disk, is **O( n ^{1/3} + (n µ(D))^{1/2}) **,
where

(iii) Let **B** be an axis parallel hypercube
in **R ^{d}**. We prove that the expected number of
points on the boundary of the quadrant hull of a set

Those bounds are known \cite bkst-anmsv-78 , but we believe the new proof is simpler.

Technical Report 330/98, School Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel, 1998.

Last modified: Tue Nov 22 13:49:43 CST 2011