Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries

 I.R. Kadyrov*, S.P. Kopysov**, A.K. Novikov***

Udmurt Federal Research Center, Ural Branch, Russian Academy of Sciences, Izhevsk, 426067 Russia

E-mail: *slasheeck@gmail.com, **s.kopysov@gmail.com, ***alexander.k.novikov@gmail.com

Received March 13, 2018

Full text PDF

Abstract

This paper considers two approaches to partitioning of a triangulated multiply connected domain into connected subdomains without branching of internal boundaries. A modified algorithm for constructing the Reeb graph for the topology determining of the triangulated surface of a three-dimensional domain has been proposed. On the basis of the partition of the Reeb graph, formation of subdomains of triangulation without branching of internal boundaries has been performed. Another approach is based on the formation of an ordered set of layers – subsets of 3-simplexes of triangulation using its topological properties, such as vertex and face connectivity. By construction, the layers do not contain branches of internal boundaries. At the same time, for multiply connected computational domains it is characteristic to obtain disconnected layers. The algorithm for combining layers into connected subdomains of triangulation has been developed based on the graph of sublayers, its vertices corresponding to the connected components of each layer. Thus, the union of layers reduces to the union of vertices and edges of the graph of sublayers – a problem with much smaller dimension, and the mapping of the partition of the graph of sublayers into triangulation. The proposed algorithms have been compared following the partitioning of triangulated multiply connected domains with surfaces of different types and genus. The complexity estimates of the algorithms have been given and the quality of the partitions by the number of 2-simplexes common for the obtained subregions of the triangulation has been compared.

Keywords: unstructured mesh, multiply connected domain, shape description, Reeb graph, graph connectivity layers, triangulation, mesh partitioning without branching

Acknowledgments. The study was partially supported by the Russian Foundation for Basic Research (projects nos. 16-01-00129-a, 17-01-00402-a).

References

1. Korneev V., Langer U. Domain decomposition methods and preconditioning. In: Encyclopedia of Computational Mechanics. Wiley-Blackwell, 2004, pp. 617–647.

2. Kopysov S.P., Kuzmin I.M., Nedozhogin N.S., Novikov A.K. Parallel algorithms for constructing and solving the Scliur complement on graphics accelerators.  Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2012, vol. 154, no. 3, pp. 202–215. (In Russian)

3. Martynenko S.I. Formalization of computations at numerical solution of boundary value problems.  Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2008, vol. 150, no. 1, pp. 76–90. (In Russian)

4. Lei Y., Baojun L., Zhangquan L., Wenbin H., Ping H. Finite element mesh deformation with the skeleton-section template. Comput.-Aided Des., 2016, vol. 43, pp. 11–25. doi: 10.1016/j.cad.2015.11.002.

5. Kopysov S.P., Kuzmin I.M., Novikov A.K., Nedozhogin N.S., Tonkov L.E. Radial basis function for parallel mesh-to-mesh interpolation in solving fluid-structure interaction problem. Izv. Inst. Mat. Inform. Udmurt. Gos. Univ., 2018, vol. 51, pp. 42–50.

6. Kopysov S.P., Novikov A.K. Parallel algorithms of adaptive refinement and partitioning of unstructured grids. Mat. Model., 2002, vol. 14, no. 9, pp. 91–96. (In Russian)

7. Yakobovskii M.V. An incremental algorithm for graph decomposition. Vestn. Nizhegorod. Univ. im. N.I. Lobachevskogo. Ser. Mat. Model. Optim. Upr., 2005, no. 1, pp. 243–250. (In Russian)

8. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput., 1998, vol. 48, pp. 96–129.

9. Novikov A.K., Kopysov S.P., Piminova N.K. Layer-by-layer partitioning of finite-element meshes for multi-core architectures. Superkomp'yuternye dni v Rossii. Trudy Mezhdunar. Konf. [Russian Supercomputing Days: Proc. Int. Conf.]. Moscow, Izd. Mosk. Univ., 2016, pp. 493–504. (In Russian)

10. Au O.K.-C., Tai C.-L., Chu H.-K., Cohen-Or D., Lee T.-Y. Skeleton extraction by mesh contraction. ACM Trans. Graph., 2008, vol. 27, no. 3, art. 44, pp. 1–10.

11. Mestetskiy L.M. Nepreryvnaya morfologiya binarnykh izobrazhenii: figury, skelety, tsirkulyary [Continuous Morphology of Binary Images: Figures, Skeletons, and Circulars]. Moscow, Fizmatlit, 2009. 288 p. (In Russian)

12. Zimovnov A.V., Mestetskiy L.M. On algorithm of curve-skeleton extraction for 3D model based on planar projections. Vestn. TvGU Ser.: Prikl. Mat., 2016, no. 3, pp. 67–83. (In Russian)

13. Ivanov A.O., Tuzhilin A.A., Fomenko A.T. Computer modeling of curves and surfaces. J. Math. Sci., 2011, vol. 172, no. 5, pp.  663–689. doi: 10.1007/s10958-011-0212-2.

14. Berretti S., Bimbo A.D., Pala P. 3D Mesh decomposition sing Reeb Graphs. Image Vision Comput., 2009, vol. 27, no. 10, pp. 1540– 1554. doi: 10.1016/j.imavis.2009.02.004.

15. Postnikov M.M. Vvedenie v teoriyu Morsa [Introduction to Morse Theory]. Moscow, Nauka, 1971. 568 p. (In Russian)

16. Hajij M., Dey T., Li X. Segmenting a surface mesh into pants using Morse theory. Graphical Models, 2016, vol. 88, pp. 12–21. doi: 10.1016/j.gmod.2016.09.003.

17. Lupescu A. Note on an algorithm for computing the Reeb graph. Int. J. Geom., 2017, vol. 6, no. 1, pp. 89–94.

18. Aho A.V., Hopcroft J.E., Ullman J.D. The Design and Analysis of Computer Algorithms. London, Amsterdam, Don Mills, Sydney, Addison-Wesley Publ. Comp., 1974. x, 470 p.

19. Harvey W., Wang Y., Wenger R. A randomized O(m log m) time algorithm for computing reeb graphs of arbitrary simplicial complexes. Proc. 26th Annu. Symp. on Computational Geometry (SoCG '10). New York, ACM, 2010, pp. 267–276.

For citation: Kadyrov I.R., Kopysov S.P., Novikov А.К. Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 3, pp. 544–560. (In Russian) 

The content is available under the license Creative Commons Attribution 4.0 License.