I am trying to implement convex hull …and i want to implement it using Divide and conquer approach …but i am unable to get any satisfactory reference.

kyu priyansh se kyu,tujhe ni ata hain,ya fir tune bhe priyansh se pucha hain kya.

There is already an algorithm that computes the convex hull of any 2D shape in just O(N lg N) time. It’s called the Graham Scan

I’m certain if you google “Graham scan”, you will find many different resources regarding that algorithm.

After some quick googling, I found a website from Princeton University regarding the Graham Scan

http://www.cs.princeton.edu/courses/archive/fall08/cos226/demo/ah/GrahamScan.html

And I’m sure there are more.

2 Likes