On the construction of the Voronoi mesh on a sphere

Jeffrey M. Augenbaum, Charles S. Peskin

Research output: Contribution to journalArticlepeer-review


A new construction of the Voronoi mesh on the sphere is presented. The main feature is that the algorithm adds points one at a time until the final Voronoi mesh is built up. By adding one point to an existing Voronoi mesh of K points, only local changes are needed to construct a Voronoi mesh of K + 1 points. This construction is particularly well suited to time-dependent problems since using information from the Voronoi mesh at the previous time step allows us to reduce the construction to O(N) operations when the two configurations are close, while the algorithm does not break down when they are far apart. Numerical experiments are presented to substantiate the O(N) operation count for a "typical" case.

Original languageEnglish (US)
Pages (from-to)177-192
Number of pages16
JournalJournal of Computational Physics
Issue number2
StatePublished - Jun 1985

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'On the construction of the Voronoi mesh on a sphere'. Together they form a unique fingerprint.

Cite this