On the Average Number of Maxima in a Set of Vectors and Applications
Jon Louis Bentley, H. T. Kung, Mario Schkolnick, Clark D. Thompson · Journal of the ACM · 1978
A maximal vector of a set ~s one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors m a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable.Solving the recurrence shows that the average number of maxmaa is O((ln n) a-~) for fixed d We use this result to construct an algorithm for finding all the maxima that have expected running tmae hnear m n (for sets of vectors drawn under our assumptions) We then use the result to find an upper bound on the expected number of convex hull points m a random point set KE~ WORDS AND eHRASES maxtma of a set of vectors, average number of maxtma, expected-tsme algorithms, analysts of algorithms, convex hulls, dynamtc programming CR CATEGORIES" 5 25, 5.39, 5.42 Permtsston to copy without fee all or part of this material ts granted provtded that the copies are not made or distributed for direct commercial advantage, the ACM copyrtght notice and the tRle of the pubhcatlon and its date appear, and notice ts gtven that copying ts by permission of the Assoctatton for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or specific permtsslon This research was supported m part by the Nattonal Soence Foundation under Grant MCS 75-222-55 and the Office of Naval Research under