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 in all components. A recurrence relation is derived for computing the average number of maximal vectors in a set of n vectors in d-space under the assumption that all n factorial to the dth power relative orderings are equally probable. Solving recurrence shows that the average number of maxima is 0((1n n) to the (d-1)th power). This result is used to construct an algorithm for finding all the maxima that has expected running time linear in n (for sets of vectors drawn under our assumptions). For a given set of random points, the result is also used to derive an upper bound on the expected number of points from the set which are on the boundary on the convex hull of the set. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1977
- Accession Number
- ADA042597
Entities
People
- C. D. Thompson
- H. T. Kung
- J. L. Bentley
- M. Schkolnick
Organizations
- Carnegie Mellon University