Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.04.2015 | Ausgabe 1/2015

Journal of Scientific Computing 1/2015

Fast Methods for Computing Centroidal Voronoi Tessellations

Zeitschrift:
Journal of Scientific Computing > Ausgabe 1/2015
Autoren:
James C. Hateley, Huayi Wei, Long Chen
Wichtige Hinweise
The first author was supported by 2010–2011 UC Irvine Academic Senate Council on Research, Computing and Libraries (CORCL) award. The second author was supported by NSFC (Grant No. 11301449), in part by Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20134301120003). The third author was supported by National Science Foundation (NSF) (DMS-0811272 and DMS-1115961), in part by 2009–2011 UC Irvine Academic Senate Council on Research, Computing and Libraries (CORCL) award, and in part by Department of Energy prime award # DE-SC0006903.

Abstract

A Centroidal Voronoi tessellation (CVT) is a Voronoi tessellation in which the generators are the centroids for each Voronoi region. CVTs have many applications to computer graphics, image processing, data compression, mesh generation, and optimal quantization. Lloyd’s method, the most widely method used to generate CVTs, converges very slowly for larger scale problems. Recently quasi-Newton methods using the Hessian of the associated energy as a preconditioner are developed to speed up the rate of convergence. In this work a graph Laplacian preconditioner and a two-grid method are used to speed up quasi-Newton schemes. The proposed graph Laplacian is always symmetric, positive definite and easy to assemble, while the Hessian, in general, may not be positive definite nor easy to assemble. The two-grid method, in which an optimization method using a relaxed stopping criteria is applied on a coarse grid, and then the coarse grid is refined to generate a better initial guess in the fine grid, will further speed up the convergence and lower the energy. Numerical tests show that our preconditioned two-grid optimization methods converges fast and has nearly linear complexity.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2015

Journal of Scientific Computing 1/2015 Zur Ausgabe

Premium Partner

    Bildnachweise