L-inf norm of a point from a line

Question

given an infinite line in 3d (either represented as $Ax=0$ or $p = p_1 + a\cdot(p_2-p_1)$ ), and a point $q$, how can one calculate the L-inf distance?

Answer 1

Here is a hint, or rather more of a suggestion for writing an algorithm to solve the problem.

You are trying to find a $t$ such that $t \mapsto \|a+tb\|_\infty$ is minimised. The function is convex and has a $\min$ (if $b=0$ any $t$ will do, if $b \neq 0$ then the function is unbounded for large $t$).

Write $f_k(t) = |a_k + t b_k|$, then we are trying to minimise $\psi(t)= \max_k f_k(t)$.

It is not hard to see that there are a finite number of points ('break points') such that on any interval between these points the function $\psi$ is affine, and the slopes are non decreasing (that is, the values of the slopes inside the interval are non decreasing as we go from left to right).

Note that a break point can occur where two different functions intersect or where one function changes from $a_k+tb_k $ to $-(a_k +bt_k)$. (If $b_k \neq 0$ then $-{a_k \over b_k}$ is a possible breakpoint.)

The goal is to find any break point where the slope switches from $\le 0$ to $\ge 0$.

Since you are in $\mathbb{R}^3$ there is a straightforward brute force means of doing this, catalogue all possible break points and the 'before & after' slopes at those points. Then sort the at most 9 points and check where the slope switches sign.

This approach can find all possible minimising $t$ if you wish.