This page will be updated frequently. Most recent update: December 13, 2004.
There is no randomized algorithm for this problem whose expected time complexity is asymptotically less than the best known deterministic algorithm, but randomization helps in other ways, as explained in the textbook.
We will also discuss an application which reduces, not to the convex hull problem, but to a variant of the convex hull problem that is so close that the same algorithms will work. This is not an untypical situation in practical applications, and shows you why "black box" packages for working standard problems have their limitations.
