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

I. R. Kadyrov   ; S. P. Kopysov   ; A. K. Novikov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 160 (2018) no. 3, pp. 544-560

Résumé

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.

Détail

Keywords: unstructured mesh, multiply connected domain, shape description, Reeb graph, graph connectivity layers, mesh partitioning without branching.
Mots-clés : triangulation

Bibliographie

[1] Korneev V., Langer U., “Domain decomposition methods and preconditioning”, Encyclopedia of Computational Mechanics, Wiley-Blackwell, 2004, 617–647

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

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

[4] Lei Y., Baojun L., Zhangquan L., Wenbin H., Ping H., “Finite element mesh deformation with the skeleton-section template”, Comput.-Aided Des., 43 (2016), 11–25 | DOI

[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., 51 (2018), 42–50 | DOI | MR

[6] Kopysov S. P., Novikov A. K., “Parallel algorithms of adaptive refinement and partitioning of unstructured grids”, Mat. Model., 14:9 (2002), 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, 243–250 (In Russian)

[8] Karypis G., Kumar V., “Multilevel k-way partitioning scheme for irregular graphs”, J. Parallel Distrib. Comput., 48 (1998), 96–129 | DOI | MR

[9] Novikov A. K., Kopysov S. P., Piminova N. K., “Layer-by-layer partitioning of finite-element meshes for multi-core architectures”, Russian Supercomputing Days, Proc. Int. Conf., Izd. Mosk. Univ., M., 2016, 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., 27:3 (2008), 44, 10 pp.

[11] Mestetskiy L. M., Continuous Morphology of Binary Images: Figures, Skeletons, and Circulars, Fizmatlit, M., 2009, 288 pp. (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, 67–83 (In Russian)

[13] Ivanov A. O., Tuzhilin A. A., Fomenko A. T., “Computer modeling of curves and surfaces”, J. Math. Sci., 172:5 (2011), 663–689 | DOI | MR | Zbl

[14] Berretti S., Bimbo A. D., Pala P., “3D Mesh decomposition using Reeb graphs”, Image Vision Comput., 27:10 (2009), 1540– 1554 | DOI

[15] Postnikov M. M., Introduction to Morse Theory, Nauka, M., 1971, 568 pp. (In Russian)

[16] Hajij M., Dey T., Li Kh., “Segmenting a surface mesh into pants using Morse theory”, Graphical Models, 88 (2016), 12–21 | DOI | MR

[17] Lupescu A., “Note on an algorithm for computing the Reeb graph”, Int. J. Geom., 6:1 (2017), 89–94 | MR | Zbl

[18] Aho A. V., Hopcroft J. E., Ullman J. D., The Design and Analysis of Computer Algorithms, Addison-Wesley Publ. Comp., London–Amsterdam–Don Mills–Sydney, 1974, x+470 pp. | MR | MR | Zbl

[19] Harvey W., Wang Y., Wenger R., “A Randomized $O(m \log m)$ time algorithm for computing Reeb graphs of arbitrary simplicial complexes”, Proc. Twenty-sixth Annual Symposium on Computational Geometry (SoCG '10), ACM, N. Y., 2010, 267–276 | MR | Zbl