Istituto di Scienza e Tecnologie dell'Informazione     
Luccio F., Preparata F. On finding the maxima of a set of vectors. Internal note IEI-B74-05, 1974.
Given a set V of n d-dimensional real vectors, a partial ordering is defined on V in a natural way. This note considers the problem of finding the maximal elements of this partial ordering. Computational complexity is expressed as the number of required comparisons of two reals. Whereas such complexity is trivially (n-1) for d=1, we describe algorithms whose complexities are of order nlog1n for d=2,3. The adopted technique. however, does not appear to be extensible to d>3, and it remains an open problem whether the straightforward upper-bound O(n2) can be improved upon for d>3.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional