Блог пользователя purple_dreams

Автор purple_dreams, история, 13 месяцев назад, По-английски,

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);
		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.

  • Проголосовать: нравится  
  • +7
  • Проголосовать: не нравится  

13 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Well if you need an O(N2) algorithm (actually it will be ) you can use monotone chain algorithm, by just storing the points in a BST (this will have complexity per insert/erase of a point). Then as monotone chain algorithm has O(N) complexity after sorting you can achieve O(N2) complexity.

By the way there is also a way to achieve fully dynamic solution explained here. You can check it out.