On finding the maxima of a set of vectors
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)< O (n 2) for d _~ 2 In this paper we show:(1) C2 (n)= O (n logan) for d= 2, 3 and Cd …
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)< O (n 2) for d _~ 2 In this paper we show:(1) C2 (n)= O (n logan) for d= 2, 3 and Cd …
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)< O (n 2) for d _~ 2 In this paper we show:(1) C2 (n)= O (n logan) for d= 2, 3 and Cd (n)~ O (n (log2n)~-~) for d~ 4,(2) C, t (n)> _ flog2 n! l for d _> 2
ACM Digital Library