Luccio F., Preparata F. On finding the maxima of a set of vectors. Internal note IEI-B74-05, 1974. |

Abstract (English) |
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. | |

Subject |

1) Download Document PDF |

Open access Restricted Private