Med tanke på en kontinuerlig skalära fält f : X → IR där X är ett topologiskt utrymme, en nivå uppsättning f är en uppsättning {x  på X : f (x) = α} för något värde α  på IR. Nivåuppsättningarna av f kan delas in i anslutna komponenter. När α ändras kontinuerligt, visas de anslutna komponenterna i nivåuppsättningarna, försvinner, delas och slås samman. Reeb- diagrammet för f kodar dessa ändringar i anslutna komponenter i nivåuppsättningar. Det ger en enkel men meningsfull abstraktion av inmatningsdomänen. Som sådan har det använts i en rad tillämpningar inom områden som grafik och vetenskaplig visualisering. I detta papper presenterar vi den första sub-kvadratiska algoritmen för att beräkna Reeb-grafen för en funktion på ett godtyckligt simplicial komplex K. Vår algoritm är randomiserad med en förväntad körtid O (m log n), där m är storleken på 2-skeletten av K (dvs. det totala antalet hörn, kanter och trianglar), och n är antalet hörn. Detta innebär en betydande förbättring jämfört med den tidigare tid komplexiteten (mn) för godtyckliga komplexa, matcher (även om i förväntan endast) det mest kända resultatet för specialfallet 2-manifolds, och är snabbare än nuvarande algoritmer för alla andra specialfall (t.ex. 3-manifolds). Vår algoritm är också mycket enkel att implementera. Preliminära experimentella resultat visar att den presterar bra i praktiken.
Harvey och Al. REF föreslår en randomiserad algoritm som beräknar Reeb-grafen för ett godtyckligt simpliciellt komplex.
A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
{'venue': "SoCG '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}