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

Abstract

A maximal vector of a set is 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 in 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)d-1) 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. © 1978, ACM. All rights reserved.