I don´t know the answer, but if someone forced me to try and stress a 2D convex hull program I would probably try adding random points from x^2 + y^2 < epsilon to random points on the boundary of a convex polygon. On Fri, Aug 9, 2013 at 7:08 PM, Henry Baker <hbaker1@pipeline.com> wrote:
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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun