Concept
Convex hull
Related concepts (38)
Star domain
In geometry, a set in the Euclidean space is called a star domain (or star-convex set, star-shaped set or radially convex set) if there exists an such that for all the line segment from to lies in This definition is immediately generalizable to any real, or complex, vector space. Intuitively, if one thinks of as a region surrounded by a wall, is a star domain if one can find a vantage point in from which any point in is within line-of-sight. A similar, but distinct, concept is that of a radial set.
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included.
Convex hull algorithms
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull.
Branch and bound
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.
Curve orientation
In mathematics, an orientation of a curve is the choice of one of the two possible directions for travelling on the curve. For example, for Cartesian coordinates, the x-axis is traditionally oriented toward the right, and the y-axis is upward oriented. In the case of a planar simple closed curve (that is, a curve in the plane whose starting point is also the end point and which has no other self-intersections), the curve is said to be positively oriented or counterclockwise oriented, if one always has the curve interior to the left (and consequently, the curve exterior to the right), when traveling on it.
Jordan curve theorem
In topology, the Jordan curve theorem asserts that every Jordan curve (a plane simple closed curve) divides the plane into an "interior" region bounded by the curve and an "exterior" region containing all of the nearby and far away exterior points. Every continuous path connecting a point of one region to a point of the other intersects with the curve somewhere. While the theorem seems intuitively obvious, it takes some ingenuity to prove it by elementary means.
Polygonal chain
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices. A simple polygonal chain is one in which only consecutive segments intersect and only at their endpoints. A closed polygonal chain is one in which the first vertex coincides with the last one, or, alternatively, the first and the last vertices are also connected by a line segment.
Convex curve
In geometry, a convex curve is a plane curve that has a supporting line through each of its points. There are many other equivalent definitions of these curves, going back to Archimedes. Examples of convex curves include the convex polygons, the boundaries of convex sets, and the graphs of convex functions. Important subclasses of convex curves include the closed convex curves (the boundaries of bounded convex sets), the smooth curves that are convex, and the strictly convex curves, which have the additional property that each supporting line passes through a unique point of the curve.