[math-fun] worst cases for 2D convex hulls ?
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?
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
Somewhat related to this - several years ago (about 15 to 25 years ago) I did a 3D renderer that rendered to the 2D surface using a Binary *Area* Tree i.e. a run-time version of a 3D BSP - using it so that the render order could be random with respect to front to back or optimised if sorted front first back last - such that the tree was created as polygons were rendered and "covered" areas of new polygons were skipped by cutting appropriately first based on the area tree. In terms of speed it was a success but in terms of the accuracy issues it was a nightmare - I suspect similar problems maybe to a lesser degree would apply to convex hulls. I say lesser degree as of course the Binary Area Tree was recursive and so, naively implemented as it was, the errors would accumulate. In case anyone's wondering why the hell I tried that - at the time there wasn't any GPU hardware at all and I think the latest 3D game out when I started it was Heretic (initial release) - and software based pixel z-depth buffering was expensive in both speed and memory. On 10 Aug 2013, at 01:08, Henry Baker 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
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
Interesting! I've been using a simple regular n-gon for testing & found some interesting facts: On at least one version of Lisp, the floating point round-off errors were so bad that a convex hull of a regular 100000-gon had only 19,992 points (20%) ! (Perhaps the poor quality of sin,cos ??) On the other hand, the exact dot-products had a _mean_ size of 138.4 bits (= quintuple 32-bit precision), in order to get all 100,000 points. Interestingly, my exact version was several times faster than the floating point version (not mine) on the same hardware, but the differing quality of the Lisp implementations might account for most/all that discrepancy. At 12:25 PM 8/10/2013, David Makin wrote:
Somewhat related to this - several years ago (about 15 to 25 years ago) I did a 3D renderer that rendered to the 2D surface using a Binary *Area* Tree i.e. a run-time version of a 3D BSP - using it so that the render order could be random with respect to front to back or optimised if sorted front first back last - such that the tree was created as polygons were rendered and "covered" areas of new polygons were skipped by cutting appropriately first based on the area tree. In terms of speed it was a success but in terms of the accuracy issues it was a nightmare - I suspect similar problems maybe to a lesser degree would apply to convex hulls. I say lesser degree as of course the Binary Area Tree was recursive and so, naively implemented as it was, the errors would accumulate.
In case anyone's wondering why the hell I tried that - at the time there wasn't any GPU hardware at all and I think the latest 3D game out when I started it was Heretic (initial release) - and software based pixel z-depth buffering was expensive in both speed and memory.
On 10 Aug 2013, at 01:08, Henry Baker 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?
participants (3)
-
David Makin -
Henry Baker -
James Buddenhagen