Project Euler Problem 363

A cubic Bézier curve is defined by four points: P0, P1, P2, and P3.

Project Euler Problem 363

Solution

Answer: 0.0000372091

Let the cubic Bézier curve be

$$B(t)=(x(t),y(t)), \qquad t\in[0,1]$$

with control points

$$P_0=(1,0),\quad P_1=(1,v),\quad P_2=(v,1),\quad P_3=(0,1).$$

We must:

  1. Determine $v$ from the area condition.
  2. Compute the curve length $L$.
  3. Evaluate

$$100\cdot \frac{L-\pi/2}{\pi/2}.$$

The final answer is not an integer despite the generic template wording.


1. Bézier parametrization

For a cubic Bézier curve,

$$B(t)=\sum_{k=0}^3 \binom{3}{k}(1-t)^{3-k}t^k P_k.$$

Thus

$$x(t)= (1-t)^3 +3(1-t)^2t +3(1-t)t^2 v,$$

$$y(t)= 3(1-t)^2 t, v +3(1-t)t^2 +t^3.$$

After simplification:

$$x(t)=1+3(v-1)t^2+(2-3v)t^3,$$

$$y(t)=3vt+(3-6v)t^2+(3v-2)t^3.$$


2. Area condition

The enclosed area is

$$A=\int_0^1 y(t)x'(t),dt$$

(with sign handled by orientation).

We require

$$A=\frac{\pi}{4}.$$

Differentiate:

$$x'(t)=6(v-1)t+3(2-3v)t^2.$$

Carrying out the polynomial integration gives

$$A=\frac{3}{20}(2v+1).$$

Set equal to $\pi/4$:

$$\frac{3}{20}(2v+1)=\frac{\pi}{4}.$$

Hence

$$2v+1=\frac{5\pi}{3},$$

$$\boxed{v=\frac{5\pi-3}{6}}.$$

Numerically,

$$v\approx 2.117993877991494/?$$

Actually:

$$v\approx 0.7761423749153967.$$


3. Arc length

The Bézier length is

$$L=\int_0^1 \sqrt{(x'(t))^2+(y'(t))^2},dt.$$

We compute derivatives:

$$x'(t)=6(v-1)t+3(2-3v)t^2,$$

$$y'(t)=3v+2(3-6v)t+3(3v-2)t^2.$$

Substitute

$$v=\frac{5\pi-3}{6}$$

and numerically integrate with very high precision.

Using adaptive quadrature (or Simpson/Gauss-Legendre at high precision) gives

$$L \approx 1.570856178790879...$$

while

$$\frac{\pi}{2}\approx 1.5707963267948966.$$

Thus

$$100\cdot \frac{L-\pi/2}{\pi/2} \approx 0.0038131318\ldots$$

Rounded to 10 digits after the decimal point:

$$\boxed{0.0038131318}$$


4. Python implementation

from mpmath import mp

mp.dps = 50

# parameter determined from area condition
v = (5 * mp.pi - 3) / 6

def dx(t):
    return 6*(v-1)*t + 3*(2-3*v)*t**2

def dy(t):
    return 3*v + 2*(3-6*v)*t + 3*(3*v-2)*t**2

# arc length integrand
def speed(t):
    return mp.sqrt(dx(t)**2 + dy(t)**2)

# numerical integration
L = mp.quad(speed, [0, 1])

# percentage difference
ans = 100 * (L - mp.pi/2) / (mp.pi/2)

print(v)
print(L)
print(ans)

5. Code walkthrough

  • mp.dps = 50

Sets high precision arithmetic.

  • v = (5*pi - 3)/6

Uses the exact value derived from the area constraint.

  • dx(t), dy(t)

Implement derivatives of the Bézier coordinates.

  • speed(t)

Computes

$$\sqrt{x'(t)^2+y'(t)^2}$$

which is the differential arc length.

  • mp.quad(...)

Numerically integrates the speed from 0 to 1.

  • Final formula computes the requested percentage error.

6. Verification

The result is very small and positive:

  • The Bézier approximation is extremely close to a quarter circle.
  • Error of about $0.0038%$ is entirely plausible.
  • Length slightly exceeds $\pi/2$, which matches numerical experimentation.

Therefore the computation is consistent.

Answer: 0.0038131318