Convex Hull (Introduction)

Convex Hull:

---

The convex hull of a set S of points in the plane is defined to be the smallest convex polygon containing all the points of S. we can define a polygon to be convex if for only two points p1 and p2 inside the polygon, the directed line segment from p1 to p2 is fully contained in the polygon

 
The main objective is to design a convex polygon path where a set of points are given. There are some algorithms to design the polygon, they are

1. Brute force ^{(Read More)}
2. Quick hull 
3. Graham's scan 
4. Jarvis's march(gift wrapping) 
5. Divide-and-Conquer 
6. Chan's algorithm(output sensitivity) 
7. Incremental 
8. Monotone Chain

Before describing about this algorithm, we have to know some geometric primitives. Next we will discuss about some geometric primitives Click Here to read...