Before revision:  2012 ) presented an (implicit) shortcuts lower bound with (As usual, and hide poly-logarithmic factors.) c+d=\Omega(n^{(D-2)/(2D-2)}).
After revision:  2012 ) presented an (implicit) shortcuts lower bound with (As usual,  hide poly-logarithmic factors.) c+d=\Omega(n^{(D-2)/(2D-2)}).