On the Average Number of Maxima in a Set of Vectors and Applications

Abstract

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