I read in an article the Euclidean distance formula can be estimated with about 6% relative error with the following formula. Would you please why this is true and where can I find such estimations? Is it possible to extend it for higher dimensions?
$d(a,b) = \max(|a_x-b_x|,|a_y-b_y|) + 0.365 \times \min(|a_x-b_x|,|a_y-b_y|) $
The original formula in the article "SOLVING LARGE VEHICLE ROUTING AND SCHEDULING PROBLEMS IN SMALL CORE", by Bordin:
On
Let $u= \max(|a_x-b_x|,|a_y-b_y|)$ and $v=\min(|a_x-b_x|,|a_y-b_y|)$, then algebra shows that $$ d(a,b)=u+r(u,v)\cdot v,\qquad r(u,v)=\frac{v}{u+\sqrt{u^2+v^2}}. $$ Why one would think that $r(u,v)\approx0.365$ always, escapes me. In fact, $r(u,v)$ can be anywhere in the interval $[0,\sqrt2-1)\approx[0,0.414)$ and $r(u,v)\approx0.365$ if and only if $v\approx0.8422\cdot u$.
Perhaps vehicle routing involves mainly points $(a,b)$ such that $v\approx0.8422\cdot u$ holds...
I will follow the notation in the previous comment. First, u itself is not a bad estimation. The maximal possible relative error with it is just $\sqrt{2}-1 < 42\% $. If it is generalized for n dimensions, then the error will be $\sqrt{n} - 1$, which means for higher dimensions this simple approximation won't work very well.
Now, let's imagine the unit circle, one point is in the center and an other one is running. At $0°$, $90°$, $180°$, $270°$ the formula u already gives a perfect result. For each running point, take the point of the corresponding radius which is as far from the center as the naive formula u estimates. Because of cosine, this curve lies on four symmetric Thales-circles, so the error function won't be very nice.
To improve the formula, we could try $u+(\sqrt{2}-1)*v$, because it provides perfect results at $45°$, $135°$, $225°$, $315°$ as well. The error is maximal at $22.5°$, it is $cos(22.5°)+(\sqrt{2}-1)*sin(22.5°)=1.0823922$.
If the formula is $u + q * v$, the error function will be $e(\alpha)=cos(\alpha)+q*sin(\alpha)$ on the proper interval. After a not very gory derivation, it seems the error is the highest at $\tan^{-1}q$ and $e(\alpha) <= S = \sqrt{1+q^{2}}$. The error is the lowest at $45°$, hence $e(\alpha) >= T = (1+q)/\sqrt{2}$. In order to keep both the highest and the lowest error values relatively low, taking $q$ where $S = 1 / T$ seems as a natural choice. After the substitutions, it boils down solving the equation $2=(1+q^2)(1+q)(1+q)$. Unfortunately the solutions are not algebraic, but the calculator tells $q=0.3392$ and using this $q$ will keep the absolute relative error under $5.5\% $.
In 3d, I'd start with something like $u\ge v\ge w, d=(\sqrt{1}-\sqrt{0})u+(\sqrt{2}-\sqrt{1})v+(\sqrt{3}-\sqrt{2})w$, although it would take some time figuring out the error guarantee.