摘要: Abstract Let C be a planar region. Choose n points p 1 ,⋯,p I.I.D. from the uniform distribution over . M number of these that are maximal. If is convex it known either E( )= Θ (√ )> or )=O( log ). In this paper we will show that, for general , there very little can said, a-priori, about More specifically if g member large class functions then always region such ( )). This contains, example, all monotically increasing form α ln β where 0 and ⩾0. also contains nondecreasing like g(n)=ln ∗ The results in remain valid higher dimensions.
elsevier.com
sci-hub.se 参考文章(7)
L. Devroye, Moment Inequalities for Random Variables in Computational Geometry Computing. ,vol. 30, pp. 111- 119 ,(1983) , 10.1007/BF02280782
Christian Buchta, On the average number of maxima in a set of vectors Information Processing Letters. ,vol. 33, pp. 63- 65 ,(1989) , 10.1016/0020-0190(89)90156-7
Mordecai J. Golin, Maxima in convex regions symposium on discrete algorithms. pp. 352- 360 ,(1993) , 10.5555/313559.313804
Luc Devroye, Lecture notes on bucket algorithms ,(1986)
Jon Louis Bentley, Hsiang-Tsung Kung, Mario Schkolnick, Clark D Thompson, On the Average Number of Maxima in a Set of Vectors and Applications Journal of the ACM. ,vol. 25, pp. 536- 543 ,(1978) , 10.1145/322092.322095
Kenneth L. Clarkson, Jon L. Bentley, David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls symposium on discrete algorithms. pp. 179- 187 ,(1990) , 10.5555/320176.320196
Rex A. Dwyer, Kinder, gentler average-case analysis for convex hulls and maximal vectors Sigact News. ,vol. 21, pp. 64- ,(1990) , 10.1145/379172.379188