Computing the convex hull of lattice points Consider a set of $n$ points in $\mathbb Z^2$. It is known that their convex hull can be computed in time $O(n\log n)$, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These bounds are in given (for instance) in the model of algebraic decision trees.

What is the bit-complexity of computing the convex hull of $n$ points in $\mathbb Z^2$, whose both coordinates are bounded in absolute value by $M$? 

I am interested on the one hand in the dependence of the complexity in $M$, and on the other hand in the possible gain in complexity one obtains using the fact that the input points have integer coordinates. In my problem, I see $M$ as a large parameter, that is $\log(M)$ has the same order of magnitude as $n$.

Note that I am especially interested in the problem with the additional requirement that the points on the convex hull have to be listed in the order of the (say) counterclockwise rotation, beginning for instance at the leftmost point.

I am also interested in the same questions in higher dimensions.
The time is essentially the same as that for sorting numbers in the range $1,\dots M$.

Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for your problem in which the coordinates are small integers, all the standard bounds of integer sorting apply. In particular, radix sort can achieve time $O(n(1+\frac{\log M}{\log n}))$ (e.g. linear time whenever $M$ is at most polynomial in $n$), and a randomized sorting algorithm of Han &amp; Thorup 2002 can achieve time $O(n\sqrt{\log\log n})$. These are in models of computation in which machine words hold integers of some word length that is big enough to store the numbers $n$ and $M$ and in which one can do arithmetic and table lookups in constant time.

Conversely, you could use a convex hull algorithm to sort a set of numbers $x_i$, by finding the hull of the points $(x_i,x_i^2)$. So if you could do convex hulls any faster than this, you could also improve the times for integer sorting. (The range $M$ of $y$-coordinates of these points would be the square of the range of the numbers, but since all the time bounds involve logarithms of this range, squaring $M$ makes no difference in terms of the eventual $O$-notation.)