Convex Hull of A Finite Point Set
The convex hull of a finite point set is the set of all convex combinations of its points. In a convex combination, each point in is assigned a weight or coefficient in such a way that the coefficients are all positive and sum to one, and these weights are used to compute a weighted average of the points. For each choice of coefficients, the resulting convex combination is a point in the convex hull, and the whole convex hull can be formed by choosing coefficients in all possible ways. Expressing this as a single formula, the convex hull is the set:
The convex hull of a finite point set forms a convex polygon in the plane, or more generally a convex polytope in . Each point in that is not in the convex hull of the other points (that is, such that ) is called a vertex of . In fact, every convex polytope in is the convex hull of its vertices.
If the points of are all on a line, the convex hull is the line segment joining the outermost two points. When the set is a nonempty finite subset of the plane (that is, two-dimensional), we may imagine stretching a rubber band so that it surrounds the entire set and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of .
In two dimensions, the convex hull is sometimes partitioned into two polygonal chains, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for points in any dimension in general position, each facet of the convex hull is either oriented upwards (separating the hull from points directly above it) or downwards; the union of the upward-facing facets forms a topological disk, the upper hull, and similarly the union of the downward-facing facets forms the lower hull.
Read more about this topic: Convex Hull
Famous quotes containing the words finite, point and/or set:
“Put shortly, these are the two views, then. One, that man is intrinsically good, spoilt by circumstance; and the other that he is intrinsically limited, but disciplined by order and tradition to something fairly decent. To the one party man’s nature is like a well, to the other like a bucket. The view which regards him like a well, a reservoir full of possibilities, I call the romantic; the one which regards him as a very finite and fixed creature, I call the classical.”
—Thomas Ernest Hulme (1883–1917)
“As for work, without it, without painstaking work, any writer or artist definitely remains a dilettante; there’s no point in waiting for so-called blissful moments, for inspiration; if it comes, so much the better—but you keep working anyway.”
—Ivan Sergeevich Turgenev (1818–1883)
“Consider what you have in the smallest chosen library. A company of the wisest and wittiest men that could be picked out of all civil countries in a thousand years have set in best order the results of their learning and wisdom. The men themselves were hid and inaccessible, solitary, impatient of interruption, fenced by etiquette; but the thought which they did not uncover in their bosom friend is here written out in transparent words to us, the strangers of another age.”
—Ralph Waldo Emerson (1803–1882)