Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Numerical Algorithms
Erschienen 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}\)

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

Erschienen in: Numerical Algorithms | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel A projection algorithm on the set of polynomials with two bounds
Nächster Artikel A fast method for variable-order space-fractional diffusion equations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
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
Metadaten
Titel
An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in
verfasst von
Phan Thanh An
Nam Dũng Hoang
Nguyen Kieu Linh
Publikationsdatum
21.03.2020
Verlag
Springer US
Erschienen in
Numerical Algorithms / Ausgabe 4/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-020-00873-1

Weitere Artikel der Ausgabe 4/2020

Numerical Algorithms 4/2020 Zur Ausgabe

Original Paper

A local meshless method for time fractional nonlinear diffusion wave equation

Original Paper

A new stable collocation method for solving a class of nonlinear fractional delay differential equations

Original Paper

Multilevel interpolation of scattered data using -matrices

Original Paper

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

Original Paper

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

Original Paper

Two energy-conserving and compact finite difference schemes for two-dimensional Schrödinger-Boussinesq equations

Premium Partner

    Bildnachweise