Related Research Articles
In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is one less than that of the ambient space. Two lower-dimensional examples of hyperplanes are one-dimensional lines in a plane and zero-dimensional points on a line.
In mathematics and specifically in algebraic geometry, the dimension of an algebraic variety may be defined in various equivalent ways.
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.
In mathematical measure theory, for every positive integer n the ham sandwich theorem states that given n measurable "objects" in n-dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single (n − 1)-dimensional hyperplane. This is even possible if the objects overlap.
In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes are removed from the whole space. One may ask how these properties are related to the arrangement and its intersection semilattice. The intersection semilattice of A, written L(A), is the set of all subspaces that are obtained by intersecting some of the hyperplanes; among these subspaces are S itself, all the individual hyperplanes, all intersections of pairs of hyperplanes, etc. (excluding, in the affine case, the empty set). These intersection subspaces of A are also called the flats ofA. The intersection semilattice L(A) is partially ordered by reverse inclusion.
Carathéodory's theorem is a theorem in convex geometry. It states that if a point lies in the convex hull of a set , then lies in some -dimensional simplex with vertices in . Equivalently, can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in , as non-extremal points can be removed from without changing the membership of in the convex hull.
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:
Any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect.
Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of dimensions. k-d trees are a useful data structure for several applications, such as:
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs". Geometric graphs are also known as spatial networks.
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the spatial median, Euclidean minisum point, Torricelli point, or 1-median.
In geometry, a flat or affine subspace is a subset of an affine space that is itself an affine space. In the case the parent space is Euclidean, a flat is a Euclidean subspace which inherits the notion of distance from its parent space.
In statistics and computational geometry, the Tukey depth is a measure of the depth of a point in a fixed set of points. The concept is named after its inventor, John Tukey. Given a set of n points in d-dimensional space, Tukey's depth of a point x is the smallest fraction of points in any closed halfspace that contains x.
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.
Kirchberger's theorem is a theorem in discrete geometry, on linear separability. The two-dimensional version of the theorem states that, if a finite set of red and blue points in the Euclidean plane has the property that, for every four points, there exists a line separating the red and blue points within those four, then there exists a single line separating all the red points from all the blue points. Donald Watson phrases this result more colorfully, with a farmyard analogy:
If sheep and goats are grazing in a field and for every four animals there exists a line separating the sheep from the goats then there exists such a line for all the animals.
Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.
Doignon's theorem in geometry is an analogue of Helly's theorem for the integer lattice. It states that, if a family of convex sets in -dimensional Euclidean space have the property that the intersection of every contains an integer point, then the intersection of all of the sets contains an integer point. Therefore, -dimensional integer linear programs form an LP-type problem of combinatorial dimension , and can be solved by certain generalizations of linear programming algorithms in an amount of time that is linear in the number of constraints of the problem and fixed-parameter tractable in its dimension. The same theorem applies more generally to any lattice, not just the integer lattice.
References
Citations
Sources
- Chan, Timothy M. (2004), "An optimal randomized algorithm for maximum Tukey depth", Proc. 15th ACM–SIAM Symp. on Discrete Algorithms (SODA 2004), pp. 430–436, ISBN 978-0-89871-558-3 .
- Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (September 1996), "Approximating center points with iterated Radon points" (PDF), International Journal of Computational Geometry & Applications, 6 (3): 357–377, doi:10.1142/S021819599600023X, MR 1409651 .
- Edelsbrunner, Herbert (1987), Algorithms in Combinatorial Geometry , Berlin: Springer-Verlag, ISBN 0-387-13722-X .
- Jadhav, S.; Mukhopadhyay, A. (1994), "Computing a centerpoint of a finite planar set of points in linear time", Discrete and Computational Geometry , 12 (1): 291–312, doi: 10.1007/BF02574382 .
- Har-Peled, S.; Jones, M. (2020-12-31), "Journey to the Center of the Point Set", ACM Transactions on Algorithms, 17 (1): 9:1–9:21, doi:10.1145/3431285, ISSN 1549-6325 .