Holes and islands in random point sets

Abstract: For

d i n m a t h b b N

, let

S

be a set of points in

m a t h b b R^{d}

in general position. A set

I

of

k

points from

S

is a

k

-island in

S

if the convex hull

m a t h r m c o n v (I)

of

I

satisfies

m a t h r m c o n v (I) c a p S = I

. A

k

-island in

S

in convex position is a

k

-hole in

S

. For

d, k i n m a t h b b N

and a convex body

K s u b s e t e q m a t h b b R^{d}

of volume

1

, let

S

be a set of

n

points chosen uniformly and independently at random from

K

. We show that the expected number of

k

-holes in

S

is in

O (n^{d})

. Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in

S

by

. This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound

O (n^{d})

even in the much more general setting, where we estimate the expected number of

k

-islands in

S

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Holes and islands in random point sets