Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries
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 dom...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2018-09-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/partitioning-of-triangulated-multiply-connected.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850105880724373504 |
|---|---|
| author | I.R. Kadyrov S.P. Kopysov A.K. Novikov |
| author_facet | I.R. Kadyrov S.P. Kopysov A.K. Novikov |
| author_sort | I.R. Kadyrov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2df3f824097e4e5cbcf3e8e876af5bc1 |
| institution | OA Journals |
| issn | 2541-7746 2500-2198 |
| language | English |
| publishDate | 2018-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета: Серия Физико-математические науки |
| spelling | doaj-art-2df3f824097e4e5cbcf3e8e876af5bc12025-08-20T02:38:58ZengKazan Federal UniversityУчёные записки Казанского университета: Серия Физико-математические науки2541-77462500-21982018-09-011603544560Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries I.R. Kadyrov0S.P. Kopysov1A.K. Novikov2Udmurt Federal Research Center, Ural Branch, Russian Academy of Sciences, Izhevsk, 426067 RussiaUdmurt Federal Research Center, Ural Branch, Russian Academy of Sciences, Izhevsk, 426067 RussiaUdmurt Federal Research Center, Ural Branch, Russian Academy of Sciences, Izhevsk, 426067 RussiaThis 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.https://kpfu.ru/partitioning-of-triangulated-multiply-connected.htmlunstructured meshmultiply connected domainshape descriptionreeb graphgraph connectivity layerstriangulationmesh partitioning without branching |
| spellingShingle | I.R. Kadyrov S.P. Kopysov A.K. Novikov Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries Учёные записки Казанского университета: Серия Физико-математические науки unstructured mesh multiply connected domain shape description reeb graph graph connectivity layers triangulation mesh partitioning without branching |
| title | Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| title_full | Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| title_fullStr | Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| title_full_unstemmed | Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| title_short | Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| title_sort | partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries |
| topic | unstructured mesh multiply connected domain shape description reeb graph graph connectivity layers triangulation mesh partitioning without branching |
| url | https://kpfu.ru/partitioning-of-triangulated-multiply-connected.html |
| work_keys_str_mv | AT irkadyrov partitioningoftriangulatedmultiplyconnecteddomainintosubdomainswithoutbranchingofinnerboundaries AT spkopysov partitioningoftriangulatedmultiplyconnecteddomainintosubdomainswithoutbranchingofinnerboundaries AT aknovikov partitioningoftriangulatedmultiplyconnecteddomainintosubdomainswithoutbranchingofinnerboundaries |