Maxima of a point set

In computational geometry, a point p in a finite set of points S is said to be maximal or non-dominated if there is no other point q in S whose coordinates are all greater than or equal to the corresponding coordinates of p. The maxima of a point set S are all the maximal points of S. The problem of finding all maximal points, sometimes called the problem of the maxima or maxima set problem, has been studied as a variant of the convex hull and orthogonal convex hull problems. 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.

For points in two dimensions, this problem can be solved in time O(n log n) by an algorithm that performs the following steps:

If the coordinates of the points are assumed to be integers, this can be sped up using integer sorting algorithms, to have the same asymptotic running time as the sorting algorithms.

For points in three dimensions, it is again possible to find the maximal points in time O(n log n) using an algorithm similar to the two-dimensional one that performs the following steps:

This method reduces the problem of computing the maximal points of a static three-dimensional point set to one of maintaining the maximal points of a dynamic two-dimensional point set. The two-dimensional subproblem can be solved efficiently by using a balanced binary search tree to maintain the set of maxima of a dynamic point set. Using this data structure, it is possible to test whether a new point is dominated by the existing points, to find and remove the previously-undominated points that are dominated by a new point, and to add a new point to the set of maximal points, in logarithmic time per point. The number of search tree operations is linear over the course of the algorithm, so the total time is O(n log n).

...
Wikipedia