[math-fun] 2D convex hull

convex hull of N points in 2D (or in 3D) can be computed in O(NlogN) steps and that is best possible in certain models of computation (e.g. algebraic decision tree model). There are many algorithms, perhaps the simplest are "randomized incremental" where you add points in random order, updating a convex hullish data structure as you go and for those algorithms the O(NlogN) is only in expectation over the randomness. For 2D, you need only to compute 3x3 determinant-signs in exact arithmetic (sign of area of a triangle), also expressible using 2x2 determinants. In general a primitive to compute sign of (D+1)x(D+1) determinant will suffice.