Bezier curve, constrained shortest path and minimum time: is the optimal curve always of minimal degree?

Question

In the unconstrained case, the shortest path between two points in arbitrary dimension is given by a straight line, which is also a Bezier curve of degree one, with two control points corresponding to the desired start and end positions.

If additional constraints apply (initial / end velocities and acceleration), the constraints are expressed using additional control points, one per constraint.

For instance, if the initial velocity is constrained, a Bezier curve of degree at least 2 is required to satisfy the constraints (3 control points).

I. Is the Bezier curve of minimum length satisfying the constraints given by the Bezier curve of minimum degree? This means, adding additional control points will not allow to find a shortest curve.

When the initial / end velocities are either unconstrained or constrained to be 0, this intuition is trivially verified.

One argument, not a proof, in favor of this theory is that the length of a Bezier curve is bounded by the perimeter of its control points: additional control points can only increase this bound.

EDIT: For this question, the answer has been proven to be no. However I think my second question stands. The minimum time seems to be a compromise between the shortest path and the minimum curvature of a curve

II. Considering linear bounds on the admissible velocities and acceleration, is the curve connecting two states in the minimum amount of time a curve of minimal degree?

EDIT 2: For this question, we'll consider a change of variable to integrate unnormalized time. If s, 0 <= s <= 1 is the parametric variable, we can introduce a total time T for the curve $\mathbf{B}(s)$ and use a change of variable to obtain a curve $\mathbf{C}(t) = \mathbf{B}(\frac{t}{T})$, which means $s = \frac{t}{T}$.

The derivatives of $\mathbf{C}(t)$ are obtained similarly to those of $\mathbf{B}(s)$, but each derivative is then premultiplied by $\frac{1}{T}$:

$\mathbf{C}'(t) = \frac{1}{T} B'(\frac{t}{T})$

We are then interested in finding the minimum value of $T$ such that the velocity / acceleration bounds are satisfied.

If for instance, the start velocity is constrained but not the end velocity, with a minimal number of control points (3), T is uniquely defined. If more control points are added, there are multiple options for both the end velocity and the minimal value of T.

My question is whether the minimum T in the minimal case T is the minimum over all possible curves of any degree that match the constraints.

Answer 1

The answer to your first question is "no".

Take the case where we constrain starting/ending locations and starting/ending directions. Suppose the start point is $A$, the end point is $C$, and the start and end tangents intersect at $B$. Clearly a quadratic Bezier curve with control points $A, B, C$ satisfies the constraints.

However, consider the cubic curve with control points $A$, $(1-k)A + kB$, $kB + (1-k)C$, $C$. If $k$ is small (say $k = 0.1$, for example), then the cubic curve is shorter than the quadratic one. In fact, as $k \to 0$, the cubic curve becomes the straight line between $A$ and $C$.

Note also that the hull of the cubic curve is contained within the hull of the quadratic one (here "hull" is a shorthand term for the convex hull of the control points). This counters your argument that increasing degree will expand hulls.

Answer 2

If by velocity you mean $\mathbf{B}'(t)$, then the diagram below shows that the answer to your first question is no. The red curve is the quadratic Bézier $(ACB)$, the green curve is the quintic Bézier $APDEQB$. Control points $P$ and $Q$ satisfy $AP/AC=BQ/BC=2/5$, so that initial and final velocities are the same for both curves. But green curve is shorter.

EDIT.

Initial velocity is $\mathbf{B}'(0)=2(C-A)$ for the quadratic Bézier and $\mathbf{B}'(0)=5(P-A)$ for the quintic Bézier. But $PA/CA=2/5$, hence those two results are equal, both in direction and magnitude. The same holds for $\mathbf{B}'(1)$.

EDIT 2.

With your definition of velocity, every Bézier curve is covered in unit time: $$ t=\int_0^L{ds\over v}=\int_0^1{|\mathbf{B}'(t)|dt\over|\mathbf{B}'(t)|}= \int_0^1dt=1. $$

Which, after all, is obvious: a point on any Bézier joining $A$ and $B$ "starts" from $A$ at $t=0$ and "arrives" at $B$ at $t=1$.

Answer 3

This picture shows two curves:

The blue one is cubic (degree 3). The red one is quartic (degree 4). The two curves have the same starting and ending first derivatives (i.e. the same starting and ending "velocities" in your terminology). More specifically, the start/end derivatives have the same directions and the same lengths.

The red curve is obviously shorter.

So, the answer to your first question is "no".