For a given finite set X and an approximation parameter \(\delta \ge 0\) , a convex polygon or polyhedron \(\mathcal{P}^\textrm{inner}\) is called an inner \(\delta \) -approximation of the convex hull \({{\,\textrm{conv}\,}}X\) of X if \({{\,\textrm{conv}\,}}X\) contains \(\mathcal{P}^\textrm{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 \({{\,\textrm{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\) 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.
