On the expected number of k-sets |
| |
Authors: | Imre Bárány William Steiger |
| |
Institution: | (1) Mathematical Institute, The Hungarian Academy of Sciences, Pf. 127, H-1364 Budapest, Hungary;(2) Department of Computer Science, Rutgers University, 08903 Piscataway, NJ, USA |
| |
Abstract: | Given a setS ofn points inR
d
, a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE
d
(k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR
d
. WhenP is spherically symmetric we prove thatE
d
(k, n)≤cn
d−1 WhenP is uniform on a convex bodyK⊂R
2 we prove thatE
2
(k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR
2 for whichE
2((n−2)/2,n) iscn logn.
The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in
part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF
Grants CCR-8902522 and CCR-9111491. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|