convex not convex
pq
p
q
pq
p
q
p1
p2
p3
p4
p5
p6
p7
p8
p9
p1, p2, p3, p4, p5, p6, p7, p8, p9
input = set of points:
output = representation of the convex hull:
p4, p5, p8, p2, p9
p q
e1
e2
destination of e1
= origin of e2
origin of e1
p
q
r
p
q
r
p1
pn
upper hull
lower hull
pi
points deleted
not a right turn
pi
pi−1
empty region
caffeine