An iterative algorithm for computing measures of generalized Voronoi regions

DOI10.1137/130935598MaRDI QIDQ2875006zbMATH OpenOpenAlexFDO

Authors Lisa J. Larsson, Jean-Christophe Nave, Rustum Choksi

Publication date 13 August 2014

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d6f18675d5993298a17ffef2e81ad9c97d6a3398

zbMATH Keywords

centroidal Voronoi tessellationseikonal equationiterative algorithmLos Angeles highway systemMarkov operatormeasures of generalized Voronoi regions

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Traffic problems in operations research (90B20)

Review text

The authors construct a new algorithm for computing the measures of generalized Voronoi regions associated with generators of arbitrary codimensions. The paper also contains several examples, the most important being the generalized Voronoi region in \(\mathbb{R}^{2}\) with nonuniform density: the Los Angeles highway system. Also interesting applications are established linked with the computation of centroidal Voronoi tessellations of general rigid objects.

Recommendations

• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations
• Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations
• Numerical studies of MacQueen's k-means algorithm for computing the centroidal Voronoi tessellations
• Centroidal Voronoi Tessellations: Applications and Algorithms

Cited in

(5)

• Geometric self-assembly of rigid shapes: a simple Voronoi approach
• A rapid approximate algorithm for computing the areas/volumes of the cells in weakly inhomogeneous Voronoi diagram
• Centroidal Power Diagrams, Lloyd's Algorithm, and Applications to Optimal Location Problems
• A fast robust algorithm for computing discrete Voronoi diagrams
• Fast Voronoi modeling

This page was built for publication: An iterative algorithm for computing measures of generalized Voronoi regions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875006)