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

Nam-Dũng Hoang (), Nguyen Kieu Linh () and Hoang Xuan Phu ()
Additional contact information
Nam-Dũng Hoang: University of Science, Vietnam National University
Nguyen Kieu Linh: Posts and Telecommunications Institute of Technology
Hoang Xuan Phu: Institute of Mathematics, Vietnam Academy of Science and Technology

Computational Optimization and Applications, 2025, vol. 91, issue 3, No 11, 1373-1413

Abstract: Abstract 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.

Keywords: Convex hull; Approximation algorithm; Approximation efficiency; Complexity; 65D18; 52B55; 65Y20; 68Q25 (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-025-00682-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:91:y:2025:i:3:d:10.1007_s10589-025-00682-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-025-00682-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().