A System of Hamilton-Jacobi Equations Characterizing Geodesic Centroidal Tessellations

doi:10.1007/s42967-023-00276-8

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (1): 289-314.doi: 10.1007/s42967-023-00276-8

Previous Articles Next Articles

A System of Hamilton-Jacobi Equations Characterizing Geodesic Centroidal Tessellations

Fabio Camilli¹, Adriano Festa²

1 Dip. di Scienze di Base e Applicate per l'Ingegneria, Sapienza Università di Roma, via Scarpa 16, Roma 00161, Italy;
2 Dip. di Scienze Matematiche "Giuseppe Luigi Lagrange", Politecnico di Torino, Corso Duca degli Abruzzi, 24, Torino 10129, Italy

Received:2022-05-27 Revised:2022-12-06 Accepted:2023-03-28 Online:2025-04-21 Published:2025-04-21
Supported by:
Open access funding provided by Politecnico di Torino within the CRUI-CARE Agreement. The present research was partially supported by MIUR Grant “Dipartimenti Eccellenza 2018-2022” CUP: E11G18000350001, DISMA, Politecnico di Torino and by the Italian Ministry for University and Research (MUR) through the PRIN 2020 project “Integrated Mathematical Approaches to Socio-Epidemiological Dynamics” (No. 2020JLWP23, CUP: E15F21005420006).

Abstract

Abstract: We introduce a class of systems of Hamilton-Jacobi equations characterizing geodesic centroidal tessellations, i.e., tessellations of domains with respect to geodesic distances where generators and centroids coincide. Typical examples are given by geodesic centroidal Voronoi tessellations and geodesic centroidal power diagrams. An appropriate version of the Fast Marching method on unstructured grids allows computing the solution of the Hamilton-Jacobi system and, therefore, the associated tessellations. We propose various numerical examples to illustrate the features of the technique.

Key words: Geodesic distance, Voronoi tessellation, K-means, Power diagram, HamiltonJacobi equation, Mean Field Games, Fast Marching method

CLC Number:

Fabio Camilli, Adriano Festa. A System of Hamilton-Jacobi Equations Characterizing Geodesic Centroidal Tessellations[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 289-314.

TrendMD

References

1. Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., Süsstrunk, S.: SLIC superpixels compared to state-of-the-art superpixel methods. IEEE Trans. Pattern Anal. Mach. Intell. 34(11), 2074–2282 (2012)
2. Alla, A., Falcone, M., Saluzzi, L.: An efficient DP algorithm on a tree-structure for finite horizon optimal control problems. SIAM J. Sci. Comput. 41, A2384–A2406 (2019)
3. Aquilanti, L., Cacace, S., Camilli, F., De Maio, R.: A mean field games approach to cluster analysis. Appl. Math. Optim. 84(1), 299–323 (2021)
4. Arthur, D., Vassilvitskii, S.: k-means++: the Advantages of Careful Seeding. In: SODA ‘07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027–1035. SIAM, PA, United States (2007)
5. Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20, 61–76 (1998)
6. Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore (2013)
7. Bardi, M., Capuzzo Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman equations. Birkhäuser, Boston (1997)
8. Bishop, C.M.: Pattern recognition and machine learning. In: Information Science and Statistics. Springer, New York (2006)
9. Bottou, L., Bengio, Y.: Convergence properties of the K-means algorithms. Adv. Neural Inf. Process. Syst. 82, 585–592 (1995)
10. Bourne, D.P., Roper, S.M.: Centroidal power diagrams, Lloyd’s algorithm, and applications to optimal location problems. SIAM J. Numer. Anal. 53(6), 2545–2569 (2015)
11. Capuzzo Dolcetta, I.: A generalized Hopf-Lax formula: analytical and approximations aspects. In: Ancona, F., Bressan, A., Cannarsa, P., Clarke, F., Wolenski, P.R. (eds) Geometric Control and Nonsmooth Analysis, pp. 136–150. World Sci. Publ., Hackensack, NJ (2008)
12. De Goes, F., Breeden, K., Ostromoukhov, V., Desbrun, M.: Blue noise through optimal transport. ACM Transactions on Graphics 31(6), 1–11 (2012)
13. Du, Q., Emelianenko, M., Ju, L.: Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Numer. Anal. 44(1), 102–119 (2006)
14. Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637–676 (1999)
15. Falcone, M., Ferretti, R.: Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2014)
16. Festa, A.: Reconstruction of independent sub-domains for a class of Hamilton-Jacobi equations and application to parallel computing. ESAIM Math. Model. Numer. Anal. 50, 1223–12401 (2016)
17. Gomes, D., Saude, J.: Mean field games—a brief survey. Dyn. Games Appl. 4(2), 110–154 (2014)
18. Kalise, D., Kunisch, K.: Polynomial approximation of high-dimensional Hamilton-Jacobi-Bellman equations and applications to feedback control of semilinear parabolic PDES. SIAM J. Sci. Comput. 40, A629–A652 (2018)
19. Lasry, J.M., Lions, P.L.: Mean field games. Jpn. J. Math. 2, 229–260 (2007)
20. Lévy, B.: A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM Math. Model. Numer. Anal. 49(6), 1693–1715 (2015)
21. Liu, Y.-J., Xu, C.-X., Yi, R., Fan, D., He, Y.: Manifold differential evolution (MDE): a global optimization method for geodesic centroidal Voronoi tessellations on meshes. ACM Trans. Graph. 35(6), 1–10 (2016)
22. Liu, Y.-J., Yu, M., Li, B.J., He, Y.: Intrinsic manifold SLIC: a simple and efficient method for computing content-sensitive superpixels. IEEE Trans. Pattern Anal. Mach. Intell. 40, 653–666 (2018)
23. Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi diagrams. 2nd Editon. John Wiley & Sons, Ltd., Chichester (2000)
24. Peyré, G., Cohen, L.: Surface segmentation using geodesic centroidal tesselation. In: Proceedings of 2nd International Symposium on 3D Data Processing, Visualization, and Transmission, pp. 995–1002. IEEE Computer Society, Washington, DC, United States (2004)
25. Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O.P., Tiwari, A., Er, M.J., Ding, W., Lin, C.T.: A review of clustering techniques and developments. Neurocomputing 267, 664–681 (2017)
26. Sethian, J.A.: Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. In: Cambridge Monographs on Applied and Computational Mathematics, 3. Cambridge University Press, Cambridge (1999)
27. Sethian, J.A., Vladimirsky, A.: Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA 97, 5699–5703 (2000)
28. Wang, J., Wang, X.: VCells: Simple and efficient superpixels using edge-weighted centroidal Voronoi tessellations. IEEE Trans. Pattern Anal. Mach. Intell. 34(6), 1241–1247 (2012)
29. Xin, S.Q., Lévy, B., Chen, Z., Chu, L., Yu, Y., Tu, C., Wang, W.: Centroidal power diagrams with capacity constraints: computation, applications, and extension. ACM Trans. Graph. 35(6), 1–12 (2016)

A System of Hamilton-Jacobi Equations Characterizing Geodesic Centroidal Tessellations

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments