Convex hull

From Academic Kids

Missing image
ConvexHull.png
Convex Hull: Elastic band analogy

In mathematics, the convex hull or convex envelope for an object or a set of objects is the minimal convex set containing the given objects. It is the minimal convex set because the convex hull is a subset of any convex set which contains the given objects.

If X is some set, the convex hull of X can be described as the set of points of the form <math>\sum_{j=1}^n t_jx_j<math>, where n is an arbitrary natural number, the numbers <math>t_j<math> are non-negative and sum to 1, and the points <math>x_j<math> are in X.

The convex hull is defined for any kind of objects a and b for which linear combinations of the form (1-t) a + t b are defined. Points in a two-dimensional plane and other geometrical objects are special cases of practical importance.

For planar objects, i.e., lying in the plane, an easy way to visualize the convex hull is to imagine a rubber band tightly stretched to encompass the given objects; when released, it will assume the shape of the required convex hull.

In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexity.

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 h, the number of points on the convex hull.

Contents

Planar case

Set of points

If not all points are on the same line, then their convex hull is a convex polygon. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of halfplanes.

Jarvis march

The simplest (although not the most time efficient) algorithm in the plane was proposed by R.A. Jarvis in 1973. It is also called gift wrapping algorithm. It has O(nh) time complexity.

Graham scan

A slightly more sophisticated, but much more efficient algorithm is the Graham scan, published in 1972 (O(n log n) time complexity).

Akl-Toussaint heuristics

The following simple heuristics is often used as the first step in implementations of convex hull algorithms to improve their performance. It is based on the efficient convex hull algorithm by S.Akl and G.T.Toussaint, 1978. The idea is to quickly exclude many points that would not be part of the convex hull anyway. This method works as follows: Find the two points with the lowest and highest x-coordinate, and the two points with the lowest and highest y-coordinate. (Each of these operations take O(n).) These four points form a quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n). (Optionally, the points with lowest and highest added x- and y-coordinate as well as those with lowest and highest subtracted x- and y-coordinate can also be determined and added, thus forming an irregular octagon, etc.)

Simple polygon

The convex hull of a simple polygon may be constructed in O(n) time.

Higher dimensions

For a finite set of points, the convex hull is a convex polyhedron. However its representation is not so simple as in the planar case. In higher dimensions, even if the vertices of a convex polyhedron are known, construction of its faces is a non-trivial task.

A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions. See http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html.

Relations to other geometric structures

See Delaunay triangulation

Applications

The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics. It also serves as a tool, a building block for a number of other computational-geometric algorithms.de:Konvexe Hlle ru:Выпуклая оболочка

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools