[go: up one dir, main page]
Scribd
Upload
45 views4 pages

Modul Convex Hull

The document discusses two algorithms for constructing the convex hull: Graham's Scan and the Monotone Chain. Graham's Scan sorts points by polar angle and operates in O(n log n) time, while the Monotone Chain also runs in O(n log n) time by first sorting points and then calculating upper and lower hulls in O(n) time. Both algorithms emphasize maintaining anti-clockwise turns and dropping clockwise turns during construction.

Uploaded by

Nasywa Syifa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
45 views4 pages

Modul Convex Hull

The document discusses two algorithms for constructing the convex hull: Graham's Scan and the Monotone Chain. Graham's Scan sorts points by polar angle and operates in O(n log n) time, while the Monotone Chain also runs in O(n log n) time by first sorting points and then calculating upper and lower hulls in O(n) time. Both algorithms emphasize maintaining anti-clockwise turns and dropping clockwise turns during construction.

Uploaded by

Nasywa Syifa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Convex Hull

Graham’s Scan
Polar angle

In case of point with minimum y value tie, choose the left most point. Polar angle sorting can also be
said as sorting the points by the angle they and the lowest point make with the X axis.

Aka. keep anti-clockwise turns and drop clockwise turns.


Graham’s scan is O(n log n) due to initial sort of angles

Monotone Chain
Constructing Lower Hull:

Aka. keep anti-clockwise turns and drop clockwise turns.

----

Constructing Upper Hull:


Pseudocode

Monotone chain algorithm constructs the convex hull in O(n log(n)) time. We have to sort the points
first and then calculate the upper and lower hulls in O(n) time.

Left-Turn/Counter-Clockwise

You might also like