I'm testing a 2D convex hull algorithm that uses _exact_ rational arithmetic. Convex hull takes a list of points and produces an ordered list going around the circumference of the convex hull of the input points. Obviously, any interior points are dropped, as are 'redundant' points _exactly on_ an edge from one hull point to another. (It turns out that most convex hull algorithms produce the list in proper order 'for free' -- i.e., for no additional work above & beyond proving that they are hull points.) (Convex hull algorithms can sometimes screw up with inexact arithmetic.) What are the worst cases for such 2D hull algorithms, both in terms of run-time and exactness ? My guess is that worst case run-times happen in the case when the points are _already_ all hull points, and that the worst-case for exactness occurs when the points are all still hull points, but get incredibly close together. My first test simply arranged points around the unit circle; exp(2*pi*i/n) in complex-speak. My second test used the standard mapping: t -> ((1-t^2)+2*t*i)/(1+t^2) to produce points around the unit circle which converged upon the point -1. If you want faster convergence, use t=s^3, or even t=s*2^s. Are there any 2D _convex_ 'fractal' patterns that might make good convex hull tests?