Gift Wrapping

If given a "gift", here defined as a random distribution of points in two or three dimensions, gift-wrapping algorithms allow programmers to find its convex hull -- the smallest convex shape that holds all interior points. This is one of the many cases where the leap from two to three dimensions leads to an incredibly more complicated code. That said, there is a rich history of algorithms to solve this problem.

To be fair, only the Jarvis March is classified as the gift wrapping algorithm; however, it's a neat name to give algorithms that solve for the convex hull of a distribution of points. Strictly speaking, though, the term is not entirely accurate for all convex hull methods.

License

Code Examples

The code examples are licensed under the MIT license (found in LICENSE.md).

Text

The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.

Pull Requests

After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:

• none