On Finding the Maxima of a Set of Vectors
H. T. Kung, Fabrizio Luccio, F. P. Preparata · Journal of the ACM · 1975
ASSTRACT.Let U1 , U2, . . ., Ud be totally ordered sets and let V be a set of n d-dimensional vectors In U~ X Us. .X Ud .A partial ordering is defined on V in a natural way The problem of finding all maximal elements of V with respect to the partial ordering ~s considered The computational complexity of the problem is defined to be the number of required comparisons of two components and is denoted by Cd(n).It is tnwal that C~(n) = n -1 and C,~(n) _ flog2 n!l for d _> 2 KEY WORDS AND PHRASES: maxima of a set of vectors, computattonal complexity, number of comparisons, algorithm, recurrence CR CATEaOmES.5.25, 5,31, 5.39 IntroductionLet U1, U2_, • • • , Ud be totally ordered sets and let V be a set of n d-dimensional vectors in the Cartesian product Ui X U2 X • • • X Ud.For any vector v in V, let x,(v) denote the zth component of v.A partial ordering < is defined on V in a natural way, that is, for v, u E V, v < u if and only if x,(v) <, x,(u) for all z = 1, ... , d, where _<, is the total ordering on U,. (We shall often write <_ for <,.The context should make clear the meaning of < .)For v C V, v is defined to be a maximal element (or, briefly, a maximum) of V if there does not exist u E V such that u ~ v and u ~ v.We consider the problem of finding all maximal elements of V.The computational complexity of the problem is defined to be Cd(n) = min max Ca(A, V),