From: schreiber@hpl.hp.com (Rob Schreiber)
Subject: Pareto Sorting
Date: 8 Mar 1999 14:29:48 -0500
Newsgroups: sci.math.num-analysis

The problem of finding the Pareto-optimal points in a set of
real d-tuples was addressed in a 1975 paper by H. T. Kung,
F. Luccio, and F. P. Preparata (On finding the maxima of a set of
vectors) which appeared in the Journal of the ACM.   I asked
Kung last year if there had been any further
progress on this problem, and he knew of none.  Their algorithm
finds the Pareto optima in a set of n d-tuples in time
O(n log n) for d = 2 and 3, and O(n log^{d-2} n) for d >= 4
(all logs are base 2.)