En slumpmässig geometrisk graf (RGG) i två dimensioner är konstruerad genom att distribuera n noder självständigt och enhetligt slumpmässigt i [0, ε n ] 2 och skapa kanter mellan varje par av noder som har Euclidean avstånd som mest r, för vissa ordinerade r. Vi analyserar följande randomiserade sändningsalgoritm på RGGs. I början informeras endast en nod från den största anslutna komponenten i RGG. Sedan, i varje omgång, väljer varje informerad nod en granne självständigt och enhetligt slumpmässigt och informerar den. Vi bevisar att med sannolikhet 1 − O(n −1 ) denna algoritm informerar varje nod i den största anslutna komponenten i en RGG inom O( ε n /r +log n) rundor. Detta gäller för valfritt värde av r som är större än det kritiska värdet för uppkomsten av en ansluten komponent med noder (n). För att bevisa detta resultat, visar vi att för två noder tillräckligt långt från varandra i [0, ε n ] 2, längden på den kortaste vägen mellan dem i RGG, när en sådan väg finns, är bara en konstant faktor större än den optimala. Detta resultat har ett oberoende intresse och, i synnerhet, ger att diametern på den största anslutna komponenten i en RGG är  och ( ε n /r), vilket överraskande har varit ett öppet problem hittills.
Frågan om sändning inom den gigantiska komponenten i ett RGG över perkoleringströskeln analyserades nyligen av Bradonjić et al. REF, som också visar att grafavståndet mellan två (tillräckligt avlägsna) noder är som mest en konstant faktor större än deras Euclidean avstånd.
Efficient broadcast on random geometric graphs
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}