A System of Hamilton-Jacobi Equations Characterizing Geodesic Centroidal Tessellations

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.

Keywords

Geodesic distance / Voronoi tessellation / K-means / Power diagram / Hamilton-Jacobi equation / Mean Field Games / Fast Marching method / 65K10 / 49M05 / 65D99 / 35F21 / 49N70

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.. 2012, 34(11): 2074-2282

[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.. 2019, 41: A2384-A2406

[3] Aquilanti L, Cacace S, Camilli F, De Maio R. A mean field games approach to cluster analysis. Appl. Math. Optim.. 2021, 84(1): 299-323

[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. 1998, 20: 61-76

[6] Aurenhammer F, Klein R, Lee DT. Voronoi Diagrams and Delaunay Triangulations. 2013, Singapore, World Scientific Publishing Company

[7] Bardi, M., Capuzzo Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman equations. Birkhäuser, Boston (1997)

[8] Bishop CM. Pattern recognition and machine learning. 2006, Springer, New York, Information Science and Statistics

[9] Bottou L, Bengio Y. Convergence properties of the K-means algorithms. Adv. Neural Inf. Process. Syst.. 1995, 82: 585-592

[10] Bourne DP, Roper SM. Centroidal power diagrams, Lloyd’s algorithm, and applications to optimal location problems. SIAM J. Numer. Anal.. 2015, 53(6): 2545-2569

[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.. 2006, 44(1): 102-119

[14] Du Q, Faber V, Gunzburger M. Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev.. 1999, 41(4): 637-676

[15] Falcone M, Ferretti R. Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. 2014, Philadelphia, PA, Society for Industrial and Applied Mathematics (SIAM)

[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.. 2016, 50: 1223-12401

[17] Gomes D, Saude J. Mean field games—a brief survey. Dyn. Games Appl.. 2014, 4(2): 110-154

[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.. 2018, 40: A629-A652

[19] Lasry JM, Lions PL. Mean field games. Jpn. J. Math.. 2007, 2: 229-260

[20] Lévy B. A numerical algorithm for L₂ semi-discrete optimal transport in 3D. ESAIM Math. Model. Numer. Anal.. 2015, 49(6): 1693-1715

[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 OP, Tiwari A, Er MJ, Ding W, Lin CT. A review of clustering techniques and developments. Neurocomputing. 2017, 267: 664-681

[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 JA, Vladimirsky A. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA. 2000, 97: 5699-5703

[28] Wang J, Wang X. VCells: Simple and efficient superpixels using edge-weighted centroidal Voronoi tessellations. IEEE Trans. Pattern Anal. Mach. Intell.. 2012, 34(6): 1241-1247

[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)

Funding

MIUR(E11G18000350001)

Politecnico di Torino

RIGHTS & PERMISSIONS

The Author(s)