In computational geometry, a point in a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...

of points is said to be ''maximal'' or ''non-dominated'' if there is no other point in whose coordinates are all greater than or equal to the corresponding coordinates of . The maxima of a point set are all the maximal points of . 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 In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding C ...

problems. It is equivalent to finding the

Pareto frontier In multi-objective optimization, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all Pareto efficient solutions. The concept is widely used in engineering. It allows the designer to restrict attention to the set of effi ...

of a collection of points, and was called the floating-currency problem by

Herbert Freeman Dr. Herbert Freeman (born Herbert Freinmann, December 13, 1925 – November 15, 2020) was an American computer scientist who made important contributions to the field of automatic label placement, computer graphics, including spatial anti-aliasi ...

based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies..

Two dimensions

For points in two dimensions, this problem can be solved in time by an algorithm that performs the following steps: *Sort the points in one of the coordinate dimensions (the -coordinate, say) *For each point, in decreasing order by -coordinate, test whether its -coordinate is greater than the maximum -coordinate of any previously processed point. (For the first point, this is

vacuously true In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she d ...

). If it is, output the point as one of the maximal points, and remember its -coordinate as the greatest seen so far. If the coordinates of the points are assumed to be

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s, this can be sped up using

integer sorting In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numb ...

algorithms, to have the same asymptotic running time as the sorting algorithms..

Three dimensions

For points in three dimensions, it is again possible to find the maximal points in time using an algorithm similar to the two-dimensional one that performs the following steps: *Sort the points in one of the coordinate dimensions (the -coordinate, say) *For each point, in decreasing order by -coordinate, test whether its projection onto the plane is maximal among the set of projections of the set of points processed so far. If it is, output the point as one of the maximal points, and remember its -coordinate as the greatest seen so far. 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 In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

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 .. For points with integer coordinates the first part of the algorithm, sorting the points, can again be sped up by integer sorting. 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 to 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 A van Emde Boas tree (), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with -bit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boa ...

in place of the balanced binary search tree. These changes to the algorithm speed up its running time to .

Higher dimensions

In any dimension the problem can be solved in time by testing all pairs of points for whether one dominates another, and reporting as output the points that are not dominated. However, when is a constant greater than three, this can be improved to . For point sets that are generated randomly, it is possible to solve the problem in linear time..

References

{{reflist Computational geometry