Andrew's Monotone Chain Convex Hull Algorithm

An Andrew's Monotone Chain Convex Hull Algorithm is a Convex Hull Algorithm that constructs the convex hull of a set of 2-dimensional points in [math]\displaystyle{ O(n \log n) }[/math] time.

• AKA: Andrew's Monotone Chain Algorithm, Andrew's Convex Hull Algorithm, Monotone Chain Algorithm.
• Context:
  • It can be implemented by a Andrew's Monotone Chain Convex Hull System to solve a Andrew's Monotone Chain Convex Hull Task.
  • …
• Example(s)
  • Wikibooks Pseudo-code Monotone Chain Algorithm,
  • Wikibooks Fortran Monotone Chain Algorithm,
  • Wikibooks JavaScript Monotone Chain Algorithm,
  • Wikibooks Java Monotone Chain Algorithm,
  • Wikibooks Python Monotone Chain Algorithm,
  • Wikibooks Ruby Monotone Chain Algorithm,
  • Wikibooks C++ Monotone Chain Algorithm,
  • Wikibooks Perl Monotone Chain Algorithm,
  • Wikibooks C Monotone Chain Algorithm,
• Counter-Example(s):
  • 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.
• See: Approximation Algorithm, Computational Geometry, Convex Polygon, Polygon, Geometriae Dedicata, Polynomial Time, Discrete And Computational Geometry.

---

---

References

2020

• (Wikibooks, 2020) ⇒ https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain Retrieved:2020-3-29.
  • QUOTE: Andrew's monotone chain convex hull algorithm constructs the convex hull of a set of 2-dimensional points in [math]\displaystyle{ O(n \log n) }[/math] time.

    It does so by first sorting the points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate), and then constructing upper and lower hulls of the points in [math]\displaystyle{ O(n) }[/math] time.

    An upper hull is the part of the convex hull, which is visible from the above. It runs from its rightmost point to the leftmost point in counterclockwise order. Lower hull is the remaining part of the convex hull.

Animation depicting the Monotone convex hull algorithm	Upper and lowers hulls of a set of points

---