Sensitivity analysis and tailored design of minimization diagrams

Birgin, E.; Laurain, A.; Menezes, T.

doi:10.1090/mcom/3839

Sensitivity analysis and tailored design of minimization diagrams
HTML articles powered by AMS MathViewer

by E. G. Birgin, A. Laurain and T. C. Menezes

Math. Comp. 92 (2023), 2715-2768

DOI: https://doi.org/10.1090/mcom/3839

Published electronically: May 12, 2023

HTML | PDF | Request permission

Abstract:

Minimization diagrams encompass a large class of diagrams of interest in the literature, such as generalized Voronoi diagrams. We develop an abstract perturbation theory in two dimensions and perform a sensitivity analysis for functions depending on sets defined through intersections of smooth sublevel sets, and formulate precise conditions to avoid singular situations. This allows us to define a general framework for solving optimization problems depending on two-dimensional minimization diagrams. The particular case of Voronoi diagrams is discussed to illustrate the general theory. A variety of numerical experiments is presented. The experiments include constructing Voronoi diagrams with cells of equal size, cells satisfying conditions on the relative size of their edges or their internal angles, cells with the midpoints of pairs of Voronoi and Delaunay edges as close as possible, or cells of varying sizes governed by a given function. Overall, the experiments show that the proposed methodology allows the construction of customized Voronoi diagrams using off-the-shelf well-established optimization algorithms.

References

R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2007), no. 4, 1286–1309. MR 2373302, DOI 10.1137/060654797
F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition 17 (1984), no. 2, 251–257. MR 765066, DOI 10.1016/0031-3203(84)90064-5
Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141–148. MR 967848, DOI 10.1093/imanum/8.1.141
H. Bennett, E. Papadopoulou, and C. Yap, Planar minimization diagrams via subdivision with applications to anisotropic Voronoi diagrams, Proceedings of the Symposium on Geometry Processing, SGP’16, Goslar, DEU, Eurographics Association, 2016, pp. 229–247.
E. G. Birgin, A. Laurain, R. Massambone, and A. G. Santana, A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls, SIAM J. Sci. Comput. 43 (2021), no. 3, A2047–A2078. MR 4267494, DOI 10.1137/20M135950X
Ernesto G. Birgin, Antoine Laurain, Rafael Massambone, and Arthur G. Santana, A shape-Newton approach to the problem of covering with identical balls, SIAM J. Sci. Comput. 44 (2022), no. 2, A798–A824. MR 4404468, DOI 10.1137/21M1426067
E. G. Birgin and J. M. Martínez, Practical augmented Lagrangian methods for constrained optimization, Fundamentals of Algorithms, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014. MR 3186234, DOI 10.1137/1.9781611973365
E. G. Birgin and J. M. Martínez, Complexity and performance of an augmented Lagrangian algorithm, Optim. Methods Softw. 35 (2020), no. 5, 885–920. MR 4144124, DOI 10.1080/10556788.2020.1746962
Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), no. 4, 1196–1211. MR 1777088, DOI 10.1137/S1052623497330963
E. G. Birgin, J. M. Martínez, and M. Raydan, Algorithm 813: SPG - software for convex-constrained optimization, ACM Trans. Math. Software 27 (2001), 340–349.
E. G. Birgin, J. M. Martínez, and M. Raydan. Spectral Projected Gradient methods. In C. A. Floudas and P. M. Pardalos, editors, Encyclopedia of Optimization, pages 3652–3659. Springer, Boston, MA, 2009.
E. G. Birgin, J. M. Martínez, and M. Raydan, Spectral projected gradient methods: review and perspectives, J. Stat. Software 60 (2014), no. 3, 1–21.
J.-D. Boissonnat, C. Wormser, and M. Yvinec. Curved Voronoi diagrams. In J.-D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, pages 67–116. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
D. P. Bourne, P. J. J. Kok, S. M. Roper, and W. D. T. Spanjer, Laguerre tessellations and polycrystalline microstructures: a fast algorithm for generating grains of given volumes, Philos. Mag. 100 (2020), 2677–2707.
David P. Bourne, Anthony J. Mulholland, Smita Sahu, and Katherine M. M. Tant, An inverse problem for Voronoi diagrams: a simplified model of non-destructive testing with ultrasonic arrays, Math. Methods Appl. Sci. 44 (2021), no. 5, 3727–3745. MR 4227954, DOI 10.1002/mma.6977
D. P. Bourne and S. M. Roper, Centroidal power diagrams, Lloyd’s algorithm, and applications to optimal location problems, SIAM J. Numer. Anal. 53 (2015), no. 6, 2545–2569. MR 3419889, DOI 10.1137/141000993
M. Budninskiy, B. Liu, F. de Goes, Y. Tong, P. Alliez, and M. Desbrun. Optimal Voronoi tessellations with Hessian-based anisotropy, ACM Trans. Graph, 35 (2016), no. 6, 242.
Aníbal Chicco-Ruiz, Pedro Morin, and M. Sebastian Pauletti, The shape derivative of the Gauss curvature, Rev. Un. Mat. Argentina 59 (2018), no. 2, 311–337. MR 3900277, DOI 10.33044/revuma.v59n2a06
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational geometry, 3rd ed., Springer-Verlag, Berlin, 2008. Algorithms and applications. MR 2723879, DOI 10.1007/978-3-540-77974-2
Frédéric de Gournay, Jonas Kahn, and Léo Lebrat, Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure, Numer. Math. 141 (2019), no. 2, 429–453. MR 3905432, DOI 10.1007/s00211-018-1000-4
M. C. Delfour and J.-P. Zolésio, Shapes and Geometries: Metrics, Analysis, Differential Calculus, and Optimization, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2011.
Qiang Du, Vance Faber, and Max Gunzburger, Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev. 41 (1999), no. 4, 637–676. MR 1722997, DOI 10.1137/S0036144599352836
Qiang Du, Max Gunzburger, and Lili Ju, Advances in studies and applications of centroidal Voronoi tessellations, Numer. Math. Theory Methods Appl. 3 (2010), no. 2, 119–142. MR 2682789, DOI 10.4208/nmtma.2010.32s.1
Herbert Edelsbrunner and Raimund Seidel, Voronoĭ diagrams and arrangements, Discrete Comput. Geom. 1 (1986), no. 1, 25–44. MR 824106, DOI 10.1007/BF02187681
Ioannis Z. Emiris, Angelos Mantzaflaris, and Bernard Mourrain, Voronoi diagrams of algebraic distance fields, Comput.-Aided Des. 45 (2013), no. 2, 511–516. MR 3041226, DOI 10.1016/j.cad.2012.10.043
Anatole Gallouët, Quentin Mérigot, and Boris Thibert, A damped Newton algorithm for generated Jacobian equations, Calc. Var. Partial Differential Equations 61 (2022), no. 2, Paper No. 49, 24. MR 4375795, DOI 10.1007/s00526-021-02147-7
R. P. Heikes, D. A. Randall, and C. S. Konor, Optimized icosahedral grids: performance of finite-difference operators and multigrid solver, Monthly Weather Rev. 141 (2013), no. 12, 4450–4469.
Antoine Henrot and Michel Pierre, Shape variation and optimization, EMS Tracts in Mathematics, vol. 28, European Mathematical Society (EMS), Zürich, 2018. A geometrical analysis; English version of the French publication [ MR2512810] with additions and updates. MR 3791463, DOI 10.4171/178
B. Joe, GEOMPACK - a software package for the generation of meshes using geometric algorithms, Adv. Eng. Software Workstations 13 (1991), 325–331.
M. Kirszbraun, Über die zusammenziehende und lipschitzsche transformationen, Fund. Math. 22 (1934), 77–108.
Jun Kitagawa, Quentin Mérigot, and Boris Thibert, Convergence of a Newton algorithm for semi-discrete optimal transport, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 9, 2603–2651. MR 3985609, DOI 10.4171/JEMS/889
Rolf Klein, Concrete and abstract Voronoĭ diagrams, Lecture Notes in Computer Science, vol. 400, Springer-Verlag, Berlin, 1989. MR 1036520, DOI 10.1007/3-540-52055-4
Jannick Kuhn, Matti Schneider, Petra Sonnweber-Ribic, and Thomas Böhlke, Fast methods for computing centroidal Laguerre tessellations for prescribed volume fractions with applications to microstructure generation of polycrystalline materials, Comput. Methods Appl. Mech. Engrg. 369 (2020), 113175, 27. MR 4117350, DOI 10.1016/j.cma.2020.113175
Antoine Laurain, Analyzing smooth and singular domain perturbations in level set methods, SIAM J. Math. Anal. 50 (2018), no. 4, 4327–4370. MR 3840889, DOI 10.1137/17M1118956
Antoine Laurain, Distributed and boundary expressions of first and second order shape derivatives in nonsmooth domains, J. Math. Pures Appl. (9) 134 (2020), 328–368 (English, with English and French summaries). MR 4053037, DOI 10.1016/j.matpur.2019.09.002
A. Laurain, Analysis and application of a lower envelope method for sharp-interface multiphase problems, arXiv:2112.02401, 2021.
Antoine Laurain and Kevin Sturm, Distributed shape derivative via averaged adjoint method and applications, ESAIM Math. Model. Numer. Anal. 50 (2016), no. 4, 1241–1267. MR 3535238, DOI 10.1051/m2an/2015075
Quentin Mérigot, Jocelyn Meyron, and Boris Thibert, An algorithm for optimal transport between a simplex soup and a point cloud, SIAM J. Imaging Sci. 11 (2018), no. 2, 1363–1389. MR 3805844, DOI 10.1137/17M1137486
Q. Mérigot, F. Santambrogio, and C. Sarrazin, Non-asymptotic convergence bounds for Wasserstein approximation using point clouds, Advances in Neural Information Processing Systems, vol. 34, Curran Associates, Inc., 2021, pp. 12810–12821.
Quentin Mérigot and Boris Thibert, Optimal transport: discretization and algorithms, Geometric partial differential equations. Part II, Handb. Numer. Anal., vol. 22, Elsevier/North-Holland, Amsterdam, [2021] ©2021, pp. 133–212. MR 4254135, DOI 10.1016/bs.hna.2020.10.001
Kaisa Miettinen, Nonlinear multiobjective optimization, International Series in Operations Research & Management Science, vol. 12, Kluwer Academic Publishers, Boston, MA, 1999. MR 1784937
Stanley Osher and James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 12–49. MR 965860, DOI 10.1016/0021-9991(88)90002-2
Marcos Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal. 13 (1993), no. 3, 321–326. MR 1225468, DOI 10.1093/imanum/13.3.321
Marcos Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim. 7 (1997), no. 1, 26–33. MR 1430555, DOI 10.1137/S1052623494266365
D. Sieger, P. Alliez, and M. Botsch, Optimizing Voronoi diagrams for polygonal finite element computations, Proceedings of the 19th International Meshing Roundtable, Berlin, Heidelberg, Springer, Berlin, Heidelberg, 2010, pp. 335–350.
Leon Simon, Lectures on geometric measure theory, Proceedings of the Centre for Mathematical Analysis, Australian National University, vol. 3, Australian National University, Centre for Mathematical Analysis, Canberra, 1983. MR 756417
Jan Sokołowski and Jean-Paul Zolésio, Introduction to shape optimization, Springer Series in Computational Mathematics, vol. 16, Springer-Verlag, Berlin, 1992. Shape sensitivity analysis. MR 1215733, DOI 10.1007/978-3-642-58106-9
V. Suppakitpaisarn, A. Ariyarit, and S. Chaidee, A Voronoi-based method for land-use optimization using semidefinite programming and gradient descent algorithm, Int. J. Geographical Inf. Sci. 35 (2021), no. 5, 999–1031.
I. E. Sutherland and G. W. Hodgman, Reentrant polygon clipping, ACM Trans. Math. Software 17 (1974), no. 1, 32–42.
Shawn W. Walker, The shapes of things, Advances in Design and Control, vol. 28, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2015. A practical guide to differential geometry and the shape derivative. MR 3486164, DOI 10.1137/1.9781611973969.ch1
C. Wormser, Generalized Voronoi diagrams and applications, Theses, Université Nice Sophia Antipolis, December 2008.
S.-Q. Xin, B. Lévy, Z. Chen, L. Chu, Y. Yu, C. Tu, and W. Wang, Centroidal power diagrams with capacity constraints: computation, applications, and extension, ACM Trans. Graph. 35 (2016), no. 6, 244.