Maxima of a point set

Last updated
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. Maxima of a point set.svg
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.

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 setS 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. [1]

Contents

Two dimensions

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

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. [3]

Three dimensions

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). [1] [2]

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 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. These changes to the algorithm speed up its running time to O(n log log n). [3]

Higher dimensions

In any dimension d the problem can be solved in time O(dn2) by testing all pairs of points for whether one dominates another, and reporting as output the points that are not dominated. However, when d is a constant greater than three, this can be improved to O(n(log n)d − 3 log log n). [4] For point sets that are generated randomly, it is possible to solve the problem in linear time. [5] [6]

Related Research Articles

Delaunay triangulation Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

Graham scan Algorithm for computing convex hulls in a set of points

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

Bounding sphere

In mathematics, given a non-empty set of objects of finite extension in -dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an -dimensional solid sphere containing all of these objects.

Euclidean minimum spanning tree

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane or higher-dimensional Euclidean space. It connects the points by a system of line segments, so that any two points can reach each other along a path through the line segments, and it selects line segments that minimize the sum of the Euclidean distances between directly-connected pairs of points.

<i>k</i>-d tree Multidimensional search tree for points in k dimensional space

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key and creating point clouds. k-d trees are a special case of binary space partitioning trees.

Klees measure problem

In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd.

The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with time complexity, where is the number of input points and is the number of points in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

Star-shaped polygon

A star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.

Monotone polygon

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice.

Minimum bounding box

In geometry, the minimum or smallest bounding or enclosing box for a point set (S) in N dimensions is the box with the smallest measure within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".

Smallest-circle problem

The smallest-circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of but worse storage of , where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings, the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .

Kenneth L. Clarkson American computer scientist

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.

In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

<i>X</i> + <i>Y</i> sorting Problem of sorting pairs of numbers by their sum

In computer science, sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers.

References

  1. 1 2 3 Preparata, Franco P.; Shamos, Michael Ian (1985), "Section 4.1.3: The problem of the maxima of a point set", Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, pp.  157–166, ISBN   0-387-96131-3 .
  2. 1 2 Kung, H. T.; Luccio, F.; Preparata, F. P. (1975), "On finding the maxima of a set of vectors" (PDF), Journal of the ACM , 22 (4): 469–476, doi:10.1145/321906.321910, MR   0381379, S2CID   2698043 .
  3. 1 2 Karlsson, Rolf G.; Overmars, Mark H. (1988), "Scanline algorithms on a grid", BIT Numerical Mathematics , 28 (2): 227–241, doi:10.1007/BF01934088, hdl: 1874/16270 , MR   0938390, S2CID   32964283 .
  4. ↑ Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), "Scaling and related techniques for geometry problems", Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), New York, NY, USA: ACM, pp. 135–143, doi:10.1145/800057.808675, ISBN   0-89791-133-4, S2CID   17752833 .
  5. ↑ Bentley, Jon L.; Clarkson, Kenneth L.; Levine, David B. (1993), "Fast linear expected-time algorithms for computing maxima and convex hulls", Algorithmica , 9 (2): 168–183, doi:10.1007/BF01188711, MR   1202289, S2CID   1874434 .
  6. ↑ Dai, H. K.; Zhang, X. W. (2004), "Improved linear expected-time algorithms for computing maxima", in Farach-Colton, Martín (ed.), LATIN 2004: Theoretical informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings, Lecture Notes in Computer Science, 2976, Berlin: Springer-Verlag, pp. 181–192, doi:10.1007/978-3-540-24698-5_22, MR   2095193 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.