Task-based Augmented Reeb Graphs with Dynamic ST-Trees

Simple item page
dc.contributor.authorGueunet, Charlesen_US
dc.contributor.authorFortin, Pierreen_US
dc.contributor.authorJomier, Julienen_US
dc.contributor.authorTierny, Julienen_US
dc.contributor.editorChilds, Hank and Frey, Steffenen_US
dc.date.accessioned2019-06-02T18:25:49Z
dc.date.available2019-06-02T18:25:49Z
dc.date.issued2019
dc.description.abstractThis paper presents, to the best of our knowledge, the first parallel algorithm for the computation of the augmented Reeb graph of piecewise linear scalar data. Such augmented Reeb graphs have a wide range of applications, including contour seeding and feature based segmentation. Our approach targets shared-memory multi-core workstations. For this, it completely revisits the optimal, but sequential, Reeb graph algorithm, which is capable of handing data in arbitrary dimension and with optimal time complexity. We take advantage of Fibonacci heaps to exploit the ST-Tree data structure through independent local propagations, while maintaining the optimal, linearithmic time complexity of the sequential reference algorithm. These independent propagations can be expressed using OpenMP tasks, hence benefiting in parallel from the dynamic load balancing of the task runtime while enabling us to increase the parallelism degree thanks to a dual sweep. We present performance results on triangulated surfaces and tetrahedral meshes. We provide comparisons to related work and show that our new algorithm results in superior time performance in practice, both in sequential and in parallel. An open-source C++ implementation is provided for reproducibility.en_US
dc.description.sectionheadersSession 1
dc.description.seriesinformationEurographics Symposium on Parallel Graphics and Visualization
dc.identifier.doi10.2312/pgv.20191107
dc.identifier.isbn978-3-03868-079-6
dc.identifier.issn1727-348X
dc.identifier.pages27-37
dc.identifier.urihttps://doi.org/10.2312/pgv.20191107
dc.identifier.urihttps://diglib.eg.org:443/handle/10.2312/pgv20191107
dc.publisherThe Eurographics Associationen_US
dc.titleTask-based Augmented Reeb Graphs with Dynamic ST-Treesen_US
Files
Original bundle
Now showing 1 - 3 of 3
Thumbnail Image
Name:
027-037.pdf
Size:
2.74 MB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
1027-file1.md
Size:
4.86 KB
Format:
Unknown data format
Download
No Thumbnail Available
Name:
1027-file2.tar
Size:
78.41 MB
Format:
Unknown data format
Download
Collections
EGPGV19: Eurographics Symposium on Parallel Graphics and Visualization