representation of the required convex shape. Output representations that have been considered for convex hulls of point sets include a list of linear inequalities describing the facets of the hull, an undirected graph of facets and their adjacencies, or the full face lattice of the hull. In two dimensions, it may suffice more simply to list the points that are vertices, in their cyclic order around the hull. For convex hulls in two or three dimensions, the complexity of the corresponding algorithms is usually estimated in terms of , the number of input points, and , the number of points on the convex hull, which may be significantly smaller than . For higher-dimensional hulls, the number of faces of other dimensions may also come into the analysis. Graham scan can compute the convex hull of points in the plane in time . For points in two and three dimensions, more complicated output-sensitive algorithms are known that compute the convex hull in time . These include Chan's algorithm and the Kirkpatrick–Seidel algorithm. For dimensions , the time for computing the convex hull is , matching the worst-case output complexity of the problem. The convex hull of a simple polygon in the plane can be constructed in linear time. Dynamic convex hull data structures can be used to keep track of the convex hull of a set of points undergoing insertions and deletions of points, and kinetic convex hull structures can keep track of the convex hull for points moving continuously. The construction of convex hulls also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set. Related structures Several other shapes can be defined from a set of points in a similar way to the convex hull, as the minimal superset with some property, the intersection of all shapes containing the points from a given family of shapes, or the union of all combinations of points for a certain type of combination. For instance: The affine hull is the smallest affine subspace of a Euclidean space containing a given set, or the union of all affine combinations of points in the set. The linear hull is the smallest linear subspace of a vector space containing a given set, or the union of all linear combinations of points in the set. The