ON THE AVERAGE NUMBER OF MAXIMA IN A SET OF VECTORS

作     者：BUCHTA, C 

作者机构：Institut für Analysis Technische Mathematik und Versicherungsmathematik Technische Universität Wien Wiedner Hauptstrasse 8-10 A-1040 Wien Austria 

出 版 物：《INFORMATION PROCESSING LETTERS》 (Inf. Process. Lett.)

年 卷 期：1989年第33卷第2期

页      面：63-65页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Average number of maxima geometric probability maxima of a set of vectors probabilistic analysis of algorithms random points 

摘      要：Any of n vectors in d -space is called maximal if none of the remaining vectors dominates it in every component. Assuming that n vectors are distributed identically and that the d components of each vector are distributed independently and continuously, we determine the expected number of maximal vectors explicitly for any n and d . The asymptotic behaviour of this quantity as n tends to infinity, which was investigated by Bentley, Kung, Schkolnick, Thompson and Devroye, follows immediately from our result.