Calculating $\max\{\min\{||B(t)-p_k||, t \in [0,1]\}, p_k \in p\}$ or at least bounding it

36 Views Asked by At

I'm trying to calculate the maximum distance from a control point $p_m = \begin{bmatrix}a_m\\b_m\end{bmatrix}$ defining a Bezier curve $B(t)$ to the closest point of the Bezier curve. For $m=0$ and $m=n$ the closest point(s) of the curve is at $t=0$ and $t=1$ respectively, and in particular $B(0) = p_0$ and $B(1) = p_n$. I'm hoping that there is a neat solution to this for other values of $m$ so that the calculation in the title of this post is relatively efficient. Unfortunately, the regular analytic method of determining relative minima and maxima using derivatives is quite messy:

$$\frac{d}{dt}\Biggr(\Bigg(\sum\limits_{k=0}^n \Big(a_k\binom{n}{k}t^k(1-t)^{n-k}\Big)-a_m\Bigg)^2+\Bigg(\sum\limits_{k=0}^n \Big(b_k\binom{n}{k}t^k(1-t)^{n-k}\Big)-b_m\Bigg)^2\Biggr)$$ $$=2\Bigg(\sum\limits_{k=0}^n \Big(a_k\binom{n}{k}t^k(1-t)^{n-k}\Big)-a_m\Bigg)\Bigg(\sum\limits_{k=0}^{n-1} \Big((a_{k+1}-a_k)\binom{n-1}{k}t^k(1-t)^{n-1-k}\Big)\Bigg)$$ $$+2\Bigg(\sum\limits_{k=0}^n \Big(b_k\binom{n}{k}t^k(1-t)^{n-k}\Big)-b_m\Bigg)\Bigg(\sum\limits_{k=0}^{n-1} \Big((b_{k+1}-b_k)\binom{n-1}{k}t^k(1-t)^{n-1-k}\Big)\Bigg)$$

Finding roots of this in terms of the $a_k$ and $b_k$ makes Matlab hang, even after trying to apply simplification and expansion methods.

I also tried finding the value(s) $t$ such that the vector $p_m-B(t)$ is orthogonal to $B'(t)$ and this calculation is listed below:

$$(a_m-B_1(t))\sum\limits_{k=0}^{n-1} \Big((a_{k+1}-a_k)\binom{n-1}{k}t^k(1-t)^{n-1-k}\Big)$$ $$+ (b_m-B_2(t))\sum\limits_{k=0}^{n-1} \Big((b_{k+1}-b_k)\binom{n-1}{k}t^k(1-t)^{n-1-k}\Big) = 0$$

This also makes Matlab hang. I'm hoping there's an easier method of evaluation, a clever simplification I missed, or just a decent enough bound on this already out there. Can anyone point me in the right direction or provide some insight themselves?