convexado

Convexado is a term used in some languages to denote the convex hull of a set. Given a finite subset S of Euclidean space, convexado(S) (often written conv(S)) is the smallest convex set that contains S. Equivalently, it is the set of all convex combinations of points in S: conv(S) = { ∑ λi xi : xi ∈ S, λi ≥ 0, ∑ λi = 1 }.

Properties of the convexado include that it is convex, it contains S, and it is unique and minimal with respect to these properties. If S is already convex, convexado(S) = S. By Carathéodory’s theorem, in R^d any point of conv(S) can be expressed as a convex combination of at most d+1 points from S.

Computing the convexado can be approached in several ways. In the plane, common algorithms such as the monotone chain (also known as Andrew’s algorithm) or Graham scan run in O(n log n) time. In higher dimensions, methods such as QuickHull or Beneath-Beyond are used, and in principle the convexado can be obtained as the intersection of all half-spaces containing S or by solving linear programs to identify extreme points.

Examples and applications illustrate its use. For S = {(0,0), (1,0), (0,1)}, convexado(S) is the triangle with those vertices. If S is collinear, the convexado is a segment or a single point. Applications include computational geometry, computer graphics, geographic information systems, robotics, and convex optimization.

Terminology note: the standard term in many fields is convex hull. Convexado is a regional or calque usage for the same concept. See also convex hull, convex combination, affine hull.