Inner δ-approximation of the convex hull of finite sets

For a given finite set X and an approximation parameter delta >= 0, a convex polygon or polyhedron P-inner is called an inner delta-approximation of the convex hull convX of X if convX contains P-inner and the Hausdorff distance between them is not greater than delta. In this paper, two algorithms for computing inner delta-approximation in 2D are developed. This approximation approach can reduce the computation time. For example, if X consists of 1,000,000 random points in an ellipse, the computation time can be reduced by 11.20% if one chooses delta to be equal to 10-4 multiplied by the diameter of this ellipse. By choosing delta=0, our algorithms can be applied to quickly determine the exact convex hull convX. Numerical experiments confirm that their time complexity is linear in n if X consists of n random points in ellipses or rectangles. Compared to others, our Algorithm 2 is much faster than the Quickhull algorithm in the Qhull library, which is faster than all 2D convex hull functions in CGAL (Computational Geometry Algorithm Library). If X consists of n=100,000 random points in an ellipse or a rectangle, Algorithm 2 is 5.17 or 18.26 times faster than Qhull, respectively. The speedup factors of our algorithms increase with n. E.g., if X consists of n=46,200,000 random points in an ellipse or a rectangle, the speedup factors of Algorithm 2 compared to Qhull are 8.46 and 22.44, respectively.