Abstrakt
Cílem článku je zkoumat očekávané chování jistých algoritmů, které byly navrženy pro spojení mezi mobilními uživateli ve dvou nebo třírozměrném prostoru. Obcný model je následující: Nechť $X$ je množina bodů v $d$-rozměrným Euklidovském prostoru $E_d$, $d\ge 2$; $r$ je funkce, která přiřazuje každému prvku $x\in X$ kladné reálné číslo $r(x)$.
Graf $G(X,r)$ je orientovaný graf s množinou vrcholů $X$, ve kterém $(x,y)$ je hrana právě když $\rho(x,y)\le r(x)$, kde $\rho(x,y)$ označuje Euklidovskou vzdálenost v prostoru $E_d$. Je-li dána množina $X$, cílem je nalézt funkci $r$ tak, aby graf $G(X,r)$ byl silně souvislý (povšimněte si, že graf $G(X,r)$ nemusí být symetrický).
Funkce $r$ vypočítávaná algoritmem podle článku je taková, že pro náhodnou množinu $X$ bodů je očekávaná hodnota $r(x)^d$ (vztahující se ke střednímu výkonu vysílače) skoro jistě konstantní.