Inner $$\delta $$ δ -approximation of the convex hull of finite sets

For a given finite set X and an approximation parameter $$\delta \ge 0$$ δ ≥ 0 , a convex polygon or polyhedron $$\mathcal{P}^\textrm{inner}$$ P inner is called an inner $$\delta $$ δ -approximation of the convex hull $${{\,\textrm{conv}\,}}X$$ conv X of X if $${{\,\textrm{conv}\,}}X$$ conv X contains $$\mathcal{P}^\textrm{inner}$$ 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$$ 1 , 000 , 000 random points in an ellipse, the computation time can be reduced by $$11.20\%$$ 11.20 % if one chooses $$\delta $$ δ to be equal to $$10^{-4}$$ 10 - 4 multiplied by the diameter of this ellipse. By choosing $$\delta = 0$$ δ = 0 , our algorithms can be applied to quickly determine the exact convex hull $${{\,\textrm{conv}\,}}X$$ conv X . 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$$ 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$$ 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.