On the Average Number of Maxima in a Set of Vectors and Applications
On the Average Number of Maxima in a Set of Vectors and Applications
复制标题
DOI：
10.1145/322092.322095
复制
发表时间：
1978-10
期刊：
影响因子：
--
通讯作者：
J. Bentley;H. T. Kung;M. Schkolnick;C. Thomborson
中科院分区：
文献类型：
--
作者：
J. Bentley;H. T. Kung;M. Schkolnick;C. Thomborson
一个集合的最大向量~S，它不小于m个分量中的任何其他向量。在假设所有(N1)个相对序都是相等概率的假设下，我们导出了计算n个向量集m~d-空间中最大向量平均个数的递推关系式。我们利用这一结果构造了一个算法来寻找所有期望在m~n附近运行的极大值(对于在我们假设下画出的向量集)，然后利用这个结果找到随机点集中期望凸包点数的一个上界
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