Convex Hull Algorithm

More than one points which have maximum y-axis value

Three points forma an angle

Compute the angle $\angle ABC$ 1. Compute the vectors: $\vec{BA}, \vec{BC}$

2. Use dot product

\[ \cos{ABC} = \frac{\vec{BA} \, \vec{BC}}{|\vec{BA}| |\vec{BC}|} \]

Eliminate Points

Point is on the left or right side of a line

N polygon

Slow Algorithm for ConvexHull

Non Cross Segments

Voronoi Diagram in Three Points

Cirlce contains no point

Non Cross Segment 2

One Point is overlapped in two segments

All segments inside Convex Hull