Abstrakt
For dELEMENT OFN, let S be a finite set of points in Rd in general position. A set H of k points from S is a \emph{k-hole} in~S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S.
A set I of k points from S is a \emph{k-island} in S if conv(I)INTERSECTIONS=I. Note that each k-hole in S is a k-island in S.
For fixed positive integers d, k and a convex body K in~Rd with d-dimensional Lebesgue measure 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-islands in S is in O(nd).
In the case k=d+1, we prove that the expected number of empty simplices (that is, (d+1)-holes) in S is at most 2d-1DOT OPERATOR d!DOT OPERATOR (nd). Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015).