How to O(n*n) online convex hull constructrion

Revision en1, by purple_dreams, 2017-05-19 10:29:16

By Graham Scan O(n*n*logn) would be possible for online construction of convex hull. Can you help me with O(n*n) algorithm. Also what is the difference between 2D CH construction and 3D CH construction

And in graham scan there is a function to sort according to polar order which i did not understand. Please help.

bool polar_order(Point a, Point b){
//ccw is a function that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise
//pivot is the lowest y-coordinate point(tie broken by lowest x-coordinate)
int order = ccw(pivot,a,b);
if(order==0)
return sqrdist(pivot,a) < sqrdist(pivot,b);
return (order==-1);
}


Also if there are some problems you know of convex hull, please share them. Thank you.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 purple_dreams 2017-05-19 10:29:16 811 Initial revision (published)