Computing the convex hull of lattice points
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.)