Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Numerical Algorithms
Published in: Numerical Algorithms 4/2020

21-03-2020 | Original Paper

An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb {R}^{n}\)

Authors: Phan Thanh An, Nam Dũng Hoang, Nguyen Kieu Linh

Published in: Numerical Algorithms | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we present an efficient improvement of gift wrapping algorithm for determining the convex hull of a finite set of points in \(\mathbb {R}^{n}\) space, applying the best restricted area technique inspired from the Method of Orienting Curves (this method was used successfully in computational geometry by An and Trang in Numerical Algorithms 59, 347–357 (2012), Optimization 62, 975–988 (2013)). The numerical experiments on the sets of random points in two- and three-dimensional space show that the running time of our algorithm is faster than the gift wrapping algorithm and the newest modified one.
previous article A projection algorithm on the set of polynomials with two bounds
next article A fast method for variable-order space-fractional diffusion equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Akl, S. G., Toussaint, G. T.: Efficient convex hull algorithms for pattern recognition applications. In: Int. Joint Conf on Pattern Recognition, Kyoto, pp. 483–487 (1978)
2.
An, P.T., Hoang, N.D., Linh, N.K., Kim, D.-S., Song, C.: The quickhull algorithm for determining the convex hull of a finite set of discs, presented at the seminar of the Voronoi Diagram Research Center. Hanyang University, Seoul, Korea. Submitted (2018)
3.
An, P.T., Trang, L.H.: An efficient convex hull algorithm for finite point sets in 3D based on the Method of Orienting Curves. Optimization 62, 975–988 (2013)MathSciNetCrossRef
4.
An, P.T., Trang, L.H.: A parallel algorithm based on convexity for the computing of Delaunay tessellation. Numer. Algorithm. 59, 347–357 (2012)MathSciNetCrossRef
5.
Bhaniramka, P., Wenger, R., Crawfis, R.: Isosurface construction in any dimension using convex hulls. IEEE Trans. Vis. Comput. Graph. 10, 130–141 (2004)CrossRef
6.
Bhattacharya, B.: Worst-Case Analysis of a Convex Hull Algorithm. Department of Computer Science, Simon Fraser University. Unpublished manuscript (1982)
7.
Bykat, A.: Convex hull of a finite set of points in two dimensions. Inf. Process. Lett., Vol. 7, 7296–298 (1978)
8.
Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret. Comput. Geom. 16, 361–368 (1996)MathSciNetCrossRef
9.
10.
Dinh, N., Phu, H.X.: Solving a class of regular optimal control problems with state constraints by the method of orienting curves. Optimization 25, 231–247 (1992)MathSciNetCrossRef
11.
Dinh, N., Phu, H.X.: Solving a class of optimal control problems which are linear in the control variable by the method of orienting curves. Acta Math. Vietnam. 17, 115–134 (1992)MathSciNetMATH
12.
Eddy, W.F.: A new convex hull algorithm for planar sets. ACM Trans. Math. Softw., Vol. 3, 398–403 (1977)
13.
Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132–133 (1972)CrossRef
14.
15.
16.
Kallay, M.: The complexity of incremental convex hull algorithms in \(\mathbb {R}^d\). Inf. Process. Lett. 19, 197 (1984)MathSciNetCrossRef
17.
Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm?. SIAM. J. Comput. 15, 287–299 (1986)MathSciNetMATH
18.
Linh, N.K., Muu, L.D.: A Convex hull algorithm for solving a location problem. RAIRO Oper. Res. 49, 589–600 (2015)MathSciNetCrossRef
19.
Linh, N.K., Song, C., Ryu, J., An, P.T., Hoang, N.D., Kim, D.-S.: QuickhullDisk: A faster convex hull algorithm for disks. Applied Mathematics and Computation 363, 124626 (2019)MathSciNetCrossRef
20.
McMullen, P., Shephard, G.C.: Convex Polytopes and the Upper Bound Conjecture. Cambridge University Press, Cambridge (1971)CrossRef
21.
O’Rourke, J.: Computational Geometry in C, 2nd edn. Cambridge University Press, Cambridge (1998)CrossRef
22.
Phu, H.X.: Zur lösung einer regulären Aufgabenklasse der optimalen Steuerung im Groß en mittels Orientierungskurven. Optimization 18, 65–81 (1987)MathSciNetCrossRef
23.
Phu, H.X.: Method of orienting curves for solving optimal control problems with state constraints. Numer. Funct. Anal. Optim. 12, 173–211 (1991)MathSciNetCrossRef
24.
Phu, H.X., Dinh, N.: Some remarks on the method of orienting curves. Numer. Funct. Anal. Optim. 16, 755–763 (1995)MathSciNetCrossRef
25.
Preparata, F.P., Shamos, M.I.: Computational Geometry. 2Nd Printing. Springer, New York (1985)CrossRef
26.
Ramaswami, S.: Convex Hulls: Complexity and Applications (A Survey) Technical Report. Department of Computer & Information Science, University of Pennsylvania (1993)
27.
Sirakov, N.M.: Search space partitioning using convex hull and concavity features for fast medical image retrieval. Biomedical Imaging: Nano to Macro, 2004. IEEE International Symposium, pp. 796–799 (2004)
28.
Sugihara, K.: Robust gift wrapping for the Three-Dimensional convex hull. J. Comput. Syst. Sci. 49, 391–407 (1994)MathSciNetCrossRef
29.
Suneeta, R.: Convex hulls: complexity and applications (a survey). University of Pennsylvania (1993)
30.
Yaacoub, F., Haman, Y., Abche, A., Fares, C.: Convex hull in medical simulations: a new hybrid approach, IECON 2006 - 32nd Annual Conference on IEEE Industrial Electronics, pp. 3308–3313
31.
Yuan, B., Tan, C.L.: Convex hull based skew estimation. Pattern Recognit. 40, 456–475 (2007)CrossRef
Metadata
Title
An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in
Authors
Phan Thanh An
Nam Dũng Hoang
Nguyen Kieu Linh
Publication date
21-03-2020
Publisher
Springer US
Published in
Numerical Algorithms / Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-020-00873-1

Other articles of this Issue 4/2020

Numerical Algorithms 4/2020 Go to the issue

Original Paper

Numerical solution of separable nonlinear equations with a singular matrix at the solution

Original Paper

Acceleration of convergence of some infinite sequences {An} whose asymptotic expansions involve fractional powers of n via the transformation

Original Paper

Analytical and numerical analysis of time fractional dual-phase-lag heat conduction during short-pulse laser heating

Original Paper

Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization

Original Paper

Variable parameter Uzawa method for solving a class of block three-by-three saddle point problems

Original Paper

A method for efficient computation of integrals with oscillatory and singular integrand

Premium Partner

    Image Credits