Convex Hull Algorithm

A Convex Hull Algorithm is a Computational Geometry Algorithm that constructs Convex Hulls of various objects.

• AKA: Convex Hull Generation Algorithm, Convex Hull Computing Algorithm.
• Context:
  • It can range from being an Online Convex Hull Algorithm to being a Dynamic Convex Hull Algorithm.
  • It can be implemented by a Convex Hull Generation System to solve Convex Hull Generation Task.
• Example(s):
  • an Andrew's Monotone Chain Algorithm,
  • a Chan's Convex Hull Algorithm,
  • a Divide and Conquer Convex Hull Algorithm,
  • a Gift Wrapping Algorithm,
  • a Graham Scan Algorithm,
  • a Kirkpatrick-Seidel Convex Hull Algorithm.
  • an Incremental Convex Hull Algorithm,
  • a Potato Peeling Algorithm,
  • a Quickhull Algorithm,
  • a ROC Convex Hull Algorithm,
  • a Simple Polygon Convex Hull Algorithm.
  • …
• Counter-Example(s):
  • an Affine Hull Algorithm,
  • a Conical Hull Algorithm.
  • a Linear Hull Algorithm,
  • a Delaunay Triangulation Algorithm,
  • a Voronoi Diagram Generation Algorithm.
• See: Data Structure, Lower Convex Envelope Function, Convex Function, Convex Layer, Combinatorial Optimization, Euclidean Plane, Euclidean Space, Bounded_Set, Convex Combination, Real Vector Space, Oriented Matroid, Closure Operator, Minkowski Sum, Projective Duality, Finite Point Set, Polygon, Brownian Motion, Space Curve, Tverberg's Theorem.

---

---

References

2020

• (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Convex_hull_algorithms Retrieved:2020-3-29.
  • 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.

---