Maxima of a point set

It is equivalent to finding the Pareto frontier of a collection of points, and was called the floating-currency problem by Herbert Freeman based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies.

The number of search tree operations is linear over the course of the algorithm, so the total time is O(n log n).

If the points are sorted separately by all three of their dimensions, the range of values of their coordinates can be reduced to the range from 1 to n without changing the relative order of any two coordinates and without changing the identities of the maximal points.

After this reduction in the coordinate space, the problem of maintaining a dynamic two-dimensional set of maximal points may be solved by using a van Emde Boas tree in place of the balanced binary search tree.

[4] For point sets that are generated randomly, it is possible to solve the problem in linear time.

The five red points are the maxima of the set of all the red and yellow points. The shaded regions show the points dominated by at least one of the five maxima.