How big is $C = frac{sum_i C_i}{n}$?
As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = Omega(n)$. I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that). Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x_1,y_1),(x_2,y_2))$ its weight is equal to $sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$
Asked By : Alex ten Brink
Answered By : Raphael
[source] Clearly, the edges could have been added in order of their weights and there are $n in mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u_i,b_j)$ with $i,j = 1,dots,k$. As $k approx frac{n}{4}$ and assuming that $n in Theta(|V|)$, both first and last row contain $Theta(|V|)$ many nodes each and the addition causes $Theta(|V|^2)$ many shortest path changes. We can now move “outwards” now, i.e. add the next edge with weight $n+2$ between $u_{k-1}$ and $b_{k-1}$ and so on; if we continue this to $(u_1,b_1)$, we cause in total $Theta(|V|^3)$ shortest path changes. If this does not convince you, note that you can actually start this “process” with $(c_1,c_2)$ and work outwards from there; this way you add $approx n$ edges which cause in total $approx sum_{i=1}^{n}i^2 in Theta(n^3) = Theta(|V|^3)$ many shortest path changes—this is just impossible to draw to fit on one screen.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1062
