# gift wrapping algorithm

> algorithm for computing convex hulls by tracing the boundary of the hull

**Wikidata**: [Q2990379](https://www.wikidata.org/wiki/Q2990379)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)  
**Source**: https://4ort.xyz/entity/gift-wrapping-algorithm

## Summary
The gift wrapping algorithm is a method for computing convex hulls by systematically tracing the boundary of the hull. It works by iteratively finding the point with the smallest polar angle relative to a reference point, which gives it an alternative name: Jarvis march.

## Key Facts
- Instance of: convex hull algorithm
- Average time complexity: O(nh)
- Worst case time complexity: O(n^2)
- Also known as: Jarvis march, algorithme d'emballage de cadeau, Algoritmo Embrulho de Presente
- Freebase ID: /m/022zv0
- Wikipedia title: Gift wrapping algorithm
- Available in multiple languages: ca, de, en, fa, fr, he, ja, ko, pl, pt
- Microsoft Academic ID (discontinued): 162935947

## FAQs
### Q: What is the gift wrapping algorithm used for?
A: The gift wrapping algorithm is used for computing convex hulls, which are the smallest convex polygons that contain all given points in a set. It works by tracing the boundary of the hull point by point.

### Q: How efficient is the gift wrapping algorithm?
A: The algorithm has an average time complexity of O(nh) and a worst-case time complexity of O(n^2), where n is the number of input points and h is the number of points in the convex hull.

### Q: Why is it called "gift wrapping"?
A: The algorithm is named "gift wrapping" because its process resembles the way one might wrap a gift by finding successive edges to include in the hull, similar to wrapping paper around an object.

### Q: What distinguishes gift wrapping from other convex hull algorithms?
A: Unlike some other convex hull algorithms, gift wrapping uses an incremental approach by tracing the hull boundary rather than dividing the point set, which makes it intuitive but potentially less efficient.

## Why It Matters
The gift wrapping algorithm is significant as one of the fundamental approaches to computing convex hulls, a problem with numerous applications in computer graphics, pattern recognition, and geographic information systems. While not always the most efficient method compared to other convex hull algorithms, its straightforward geometric intuition makes it valuable for educational purposes and for situations where simplicity is prioritized over performance. The algorithm's ability to incrementally build the hull by finding the next point with the smallest polar angle provides an elegant solution to a problem that has practical importance in various computational geometry applications.

## Notable For
- Simple geometric intuition that makes it easy to understand and implement
- Ability to handle any dimensional convex hulls
- Incremental approach that allows for streaming data processing
- Multiple language implementations and documentation worldwide
- Educational value as an introductory example of computational geometry algorithms

## Body

### Algorithm Overview
The gift wrapping algorithm is a method for computing convex hulls by systematically finding the extreme points of a set. It works by tracing the boundary of the hull, identifying each successive point that forms the smallest angle with the current edge.

### Time Complexity
- Average time complexity: O(nh)
- Worst case time complexity: O(n^2)
Where n is the number of input points and h is the number of points in the convex hull.

### Alternative Names
The algorithm is known by several names across different contexts:
- Jarvis march (after its inventor)
- Algorithme d'emballage de cadeau (French)
- Algoritmo Embrulho de Presente (Portuguese)

### Implementation
The algorithm is available on GitHub under the topics "jarvis-march" and "gift-wrapping", indicating active development and community interest.

### Cultural Presence
The algorithm has been documented in multiple Wikipedia languages including Catalan, German, English, Persian, French, Hebrew, Japanese, Korean, Polish, and Portuguese, demonstrating its international relevance.

### Academic Recognition
The algorithm has been assigned the Microsoft Academic ID 162935947 (now discontinued) and is recognized in Freebase with ID /m/022zv0.

### Relationship to Other Algorithms
As an instance of convex hull algorithm, it belongs to a broader class of computational geometry methods that solve related but potentially more efficient problems.

## References

1. Freebase Data Dumps. 2013