Search

Given a set S of n points in R , a subset X of size d is called a k-simplex if the hyperplane aff( X) has exactly k points on one side. We study E (k,n), the expected number of k-simplices when S is a random sample of n points from a probability distribution P on R . When P is spherically symmetric we prove that E (k, n)≤ cn When P is uniform on a convex body K⊂ R we prove that E (k, n) is asymptotically linear in the range cn≤ k≤ n/2 and when k is constant it is asymptotically the expected number of vertices on the convex hull of S. Finally, we construct a distribution P on R for which E (( n−2)/2, n) is cn log n. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane Π that separates X from S−X. We prove that O( n√ k/log* k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log* k. [ABSTRACT FROM AUTHOR]