Reeb-grafen spårar topologiförändringar i nivåuppsättningar av en skalarfunktion och finner tillämpningar i vetenskaplig visualisering och geometrisk modellering. Vi beskriver en algoritm som konstruerar Reeb-grafen av en Morse-funktion definierad på en 3-manifold. Vår algoritm upprätthåller anslutna komponenter av de två dimensionsnivåerna som en dynamisk graf och konstruerar Reeb-grafen i O(n log n + n log g(log log g) 3 ) tid, där n är antalet trianglar i tetrahedral mesh som representerar 3-manifold och g är det maximala släktet över alla nivåuppsättningar av funktionen. Vi utökar denna algoritm för att konstruera Reeb grafer av d-manifolder i O(n log n(log log n) 3 ) tid, där n är antalet trianglar i simplial komplexet som representerar d-manifold. Vårt resultat är en betydande förbättring jämfört med den tidigare kända O(n 2 ) algoritmen. Slutligen presenterar vi experimentella resultat av vårt genomförande och visar att vår algoritm för 3-manifolder i praktiken presterar bättre än vad den teoretiska gränsen antyder.
Doraiswamy och Natarajan REF utvidgade ytterligare den svepande idén för att hantera 3-manifolder, och presenterade en O(m log m+m log g(logglogg g)
Efficient Algorithms for Computing Reeb Graphs
{'venue': 'Comput. Geom.', 'journal': 'Comput. Geom.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}