Effektiviteten i att extrahera topologisk information från punktdata beror till stor del på det komplex som är byggt ovanpå datapunkterna. Ur beräkningssynpunkt har de mest gynnade komplexen för detta ändamål hittills varit Vietoris-Rips och vittneskomplex. Medan VietorisRips komplex är enkelt att beräkna och är ett bra fordon för att extrahera topologi av provutrymmen, är dess storlek enorm särskilt i höga dimensioner. Vittneskomplexet å andra sidan har en mindre storlek på grund av en subsampling, men misslyckas med att fånga topologin i höga dimensioner om inte påtvingas med extra strukturer. Vi undersöker ett komplex som kallas grafen framkallade komplex som, i viss utsträckning, har fördelarna med båda. Det fungerar på ett delprov men behåller fortfarande kraften i att fånga topologin som Vietoris-Rips-komplexet. Den behöver bara en graf som förbinder de ursprungliga provpunkterna från vilka den bygger ett komplex på delprovet och därmed tämjer storleken avsevärt. Vi visar att med hjälp av grafen framkallade komplexet kan man (i) härleda den endimensionella homologin hos ett grenrör från ett mycket magert delprov, (ii) rekonstruera en yta i tre dimensioner från ett glest delprov utan att beräkna Delaunay triangulations, (iii) härleda de ihållande homologigrupperna av kompakta uppsättningar från ett tillräckligt tätt prov. Vi tillhandahåller experimentella bevis till stöd för vår teori.
Med tanke på en graf konstruerad på en punkt moln som ingång, grafen inducerade komplexet är en simplial komplex byggt på en delmängd av hörn, där hörnen i en k-simplex är de närmaste grannarna till en klique-vertikes av en k-clique REF.
Graph induced complex on point data
{'venue': "SoCG '13", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}