Benutzer:Georg-Johann/Mathematik

A Julia Set (in white) visualized using CCA

 

Visualising Julia sets

Julia sets and Fatou sets can be nice. Their computergraphical generation can be hard.

In the remainder of this page, we work out a method which can be used to visualise the Julia set of a complex function ƒ. The advantage is that you don't need to know attractors of the iteration

$z\mapsto f(z)$

The generated images will be smooth in the Fatou part.

Overview: Imaging methods

Note that there exist other approaches to color complex dynamical systems like

Inverse Iteration Method (IIM)

Compute the preimages of ƒ, i.e. compute the reverse orbit. Because the stability of the fixed points turns from attractive to repelling and vice versa, one just choses a complex number and looks where it goes under the invers iteration. The trouble is that the results will not uniformly distributet in $J$ and that you have to compute the inverse of ƒ.

Coloring by speed of attraction (CSA)

Taking a value from the lattice of points to color, perform iterations until the iterative is close to an attractor. Color the point according to the number of iterations needed to bring it close enough to the attractor.

This method is commonly used to visualize Julia sets of polynomials and Julia sets that are attached to Newton's famous method for finding the zeros of a function. Polynomials always have infinity as an attractive fixed point. The rational function that occurs in Newton's method has always the function's roots as attractive fixed points. However, in both cases there may be other attractors, which – moreover – need not to consist of just one point.

A special case of CSA is an approach sometimes called

Escape Time Algorithm (ETA)

If ∞ is an attractor, i.e. a fixed point of the process, then color the point according to the number of iterations – the time – it takes until one sees the point escapes towards ∞. If the point does not escape during the maximum number of iterations, the point is colored as belonging to the Julia set or to the basin of some other attractor. This method works for polynomials. The most prominent Julia sets are the ones for z→z²+c where c is an element of the Mandelbrot set or not far away from the mandelbrot set. If you see a picture of such a Julia set, it is likely that ETA had been used to get the picture.

Cauchy Convergence Algorithm (CCA)

In the remainder of this page, I will present a different approach whose idea as basically the same es that of Escape Time Algorithm. However, no basin of attraction must be known in advance and the different basins of attraction can be separated and be colored differently. The approch uses the notion of Cauchys convergence. Instead of observing the orbit of a point, this method observes how the distance of two nearby points z and z+ε evolves as these two values are iterated. If the difference tends to 0, then the point heads for an attractor. If the difference does not approach 0, then the point is close to (or a part of) the Julia set.

The Metric

Let $\varrho$ be a canonical projection of the compactified complex plane onto the Riemann sphere S₂:

$\varrho :{\overline {\mathbb {C} }}=\mathbb {C} \cup \{\infty \}\rightarrow S_{2}$

This gives us a metric $d$: As distance between two points in the complex plane we take their distance on the sphere, i.e. the length of the orthodrome. This means that the metric is bounded by $\pi$ and even the distance to ∞ (which is now the north pole) is finite.

In order to compute the distance between two points $z$ and $w$ we rotate the sphere S₂ in such a way that

1. $w$ maps to 0
2. $z$ maps to the positive real axis

After these transformations the distance can be computed quite easily. The rotation can be accomplished by a squence of isometric Möbius transformations. All an all, we get

$t_{w}:z\mapsto {\begin{cases}|z|\;,&{\text{ if }}w=0\\{\textstyle {\frac {1}{|z|}}}\;,&{\text{ if }}w=\infty \\{\textstyle {\frac {1}{|w|}}}\;,&{\text{ if }}z=\infty \\&\\{\textstyle {\frac {1}{|w|}}}\cdot \left|{\frac {z{\overline {w}}-|w|^{2}}{z{\overline {w}}+1}}\right|\;,&{\text{ else}}\end{cases}}$

which is left as an exercise to the reader. The bar denotes complex conjugation. The metric is then

$d(z,w)=\,\!2\arctan(t_{w}(z))$

The nice feature that is introduced by d is that sequences that formerly diverged against infinity now converge towards infinity, i.e. towards the north pole of S₂.

Stability of Orbits

Recall the definition of the Julia set for a contraction mapping ƒ. The definition implies some facts on the stability of the iteration

$z\mapsto f(z)\mapsto f^{2}(z)\mapsto f^{3}(z)\mapsto \cdots$

where ƒⁿ denotes the n-th iterative of ƒ:

$f^{\,n}=f\circ f\circ \cdots \circ f$

The set

$\{f^{\,n}(z)\}_{n\in \mathbb {N} _{0}}$

is called Orbit of z (under ƒ).

The orbits of two points z and w behave similar − in some sense − if z and w lie close together and belong to the Fatou set F_ƒ which is the complement of the Julia set J_ƒ of ƒ. If z is an element of J_ƒ then z and w will behave quite different, even if w itself is an element of J_ƒ.

To get a notion of the stability of an orbit, we set

$\Sigma _{n}(z)=\Sigma _{n}(z,\varepsilon )=\sum _{k\leqslant n}d\,(f^{k}(z),f^{k}(z+\varepsilon ))$

for a small ε and with the metric d from above. This means that we take two points which are close together, and then we summarize their distances as ƒ makes them jump around on the Riemann sphere. Note that for any fixed ε the sum can diverge for large n even if z is a Fatou point.

However, we can use Σ_n to measure how close a point is to J_ƒ: the larger the sum is, the more instable is the iteration and the closer is the point to the Julia set of ƒ.

To destinguish points of (or close to) the Julia set from points in the Fatou set, we need a creterion. To get it, we compute all the Σ-values for the points that we want to color, i.e. for all points in a lattice Γ. After computing these values, we do a little bit of statistics to get the expected value E and the standard deviation σ for the set of Σ-values: Let

${\begin{aligned}E_{n}&=E_{n}(\Gamma ,\varepsilon )=E\left\{\log(\delta +\Sigma _{n}(z,\varepsilon ))\right\}_{\!z\,\in \,\Gamma }\\\sigma _{n}&={\sqrt {D_{n}}}\\\end{aligned}}$

Remind that

${\begin{aligned}EX&={\textstyle {\frac {1}{|X|}}}\sum \limits _{x\in X}x\\D\!X&=EX^{2}-(EX)^{2}\\\end{aligned}}$

It turns out that the values Σ are widely spread over several scales. Therefore, we do not use Σ directly. Instead, we use the logarithm of Σ. The value δ is just a small constant to avoid the logarithm's input to be zero.

Coloring

Now, we have all we need to color a point:

1. choose
   1. a lattice $\Gamma$ of points $z$ to color
   2. the number $n$ of iterations to perform
   3. a small $\varepsilon$
2. for all points, compute $\Sigma _{n}(z,\varepsilon )$
3. compute $E_{n}$ and $\sigma _{n}$
4. compute

$J(z)=\,\ln(\delta +\Sigma _{n}(z))-K$

for some constant $K$. Because $K$ will be used to separate points that belong to the Julia set ($J(z)>0$) from points that to not ($J<0$), reasonable values for $K$ are greater than $E_{n}$. Try settings like $K=E_{n}+2\sigma _{n}$ or $E_{n}+\sigma _{n}$ or the like. If $J(z)>0$ then we color $z$ as belonging to the Julia set. If $J(z)<0$ we can use that value to shade the Fatou set. If we know some attractor, we can check if ƒ^$n$$(z)$ is close to it and use that information, too.

To map values to the valid ranges for saturation and brightness we use the function $h$ from section helper function h.

Modifications

The computation of $E_{n}$ takes a lot of time. The visualisation process needs two passes:

1. compute $E_{n}$ from all $\Sigma _{n}(z)$
2. color the points using $E_{n}$ and recomputed $\Sigma _{n}(z)$

Alternatively

1. compute and store all $\Sigma _{n}(z)$
2. compute $E_{n}$ and color the points

An other approach looks like that:

Find the smallest $n$ so that $d_{k}(z,z+\varepsilon )$ is below a given bound for all $k\geq n$. If no such $n$ can be found, then assume $z$ to be an element of the Julia set. Otherwise, use $n$ to color the Fatou set.

This algorithm is a variant of the escape time algorithm (ETA). Note that in ETA the point does not really escape (at least if we are on the sphere), it just converges to ∞. This approach is similar. However, we don't need to know an attractive fixed point of ƒ.

Up to now, I didn't try the modified version. One disadvantage may be that the Fatou set will no more appear smooth colored. Then I am not sure if this modification is really an advantage, because the iteration must be done until a given maximum number of iterations is reached. Note that even if $d_{n}$ is under the bound for some $n$ the distance $d_{k}$ can rise again. I cannot say if this effect is crucial or can be neglected...

Gallery

• 
  $z\mapsto z^{2}$
• 
  $z\mapsto z^{2}+i$
• 
  $z\mapsto z^{2}-1$
• 
  ${}_{z\mapsto z^{2}-0.742+i/10}$
• 
  $z\mapsto N_{z^{3}-1}$
• 
  $z\mapsto N_{z^{3}-2z+2}$

$N$ denotes the Newton operator

$N:f\mapsto {\mathit {id}}-{\frac {f}{f'}}$

Visualising complex functions

Color space in HSV-projection

Suppose we want to visualise a complex valued function like

${\begin{aligned}f:\mathbb {C} &\;\to \mathbb {C} \\z&\;\mapsto w=f(z)\\\end{aligned}}$

In order to color $w$ we decompose it into its absolute value $|w|$ and its argument $\arg(w)$.

Then, we assign the color

$\mathrm {HSV} \left({\tfrac {1}{2\pi }}\arg(w),\;1-g_{a_{s},b_{s}}(|w|),\;g_{a_{v},b_{v}}(|w|)\right)$

to the point representing $z$. In this HSV color space, all values are in the range from 0 to  1. The first component (hue) of the HSV color depends only on the argument of $w$ and the second and third component (saturation and value) depend only on the absolute value of $w$. We use a transformation $g_{a,b}$ on $w$ to map it into the interval $[0,1]$. For $g$ see section helper functions.

Examples

The values indexed s (saturation) control the transition saturated colors→white (resp. gray scale), i.e. intermediate values → infinity. The values indexed h (value/valenz) control the transition black→bright, i.e. zero→nonzero. Parameter a controls where the transition takes place: a is just the radius of the circle dividing the two regions (dark/bright, saturated/gray, etc.) Parameter b controls how sharp the transition is: b small = soft, b large = sharp.

The following images all show the range [-10,10]×[-10,10]$i$ and use $a_{s}=5$ (radius of rainbow) and $a_{v}=1$ (radius of black disc).

In the image with swapped meanings of S and V zero is printed in white and infinity in black.

Gallery

• Some examples of colorings
• 
  $b_{s}=b_{v}=10$
• 
  $b_{s}=b_{v}=1$
• 
  $b_{s}=0.05,b_{v}=1/3$
• 
  $b_{s}=0.05,b_{v}=1/3$
  Roles of S and V interchanged

• Analysis of critical point of z→z²+c
• 
  n=1: starting values (color map)
• 
  n=2
• 
  n=3
• 
  n=4
• 
  n=17
• 
  n=18
• 
  n=19
• 
  n=20

Helper functions

Helper function t

some $t\,$

is a smooth transition from −1 to 1 that satisfies $t'(0)=1$ and $t(x)=-t(-x)$. There are many choices for it. Some of them are

${\begin{aligned}t:\mathbb {R} &\to (-1,1)\\x&\mapsto \tanh \,x\\&\mapsto {\tfrac {2}{\pi }}\arctan \left({\tfrac {\pi }{2}}x\right)\\&\mapsto {\tfrac {2}{\pi }}\operatorname {gd} \left({\tfrac {\pi }{2}}x\right)\\&\mapsto {\frac {x}{\sqrt {1+x^{2}}}}\\&\mapsto {\frac {x}{1+|x|}}\\\end{aligned}}$

with gd denoting the gudermannian function.

Helper function h

$h_{a}\,$

Helper function $h_{a}$ is almost the same like $t$ but it maps to $(0,1)$ and we can adjust the speed of transition by parameter $a$.

${\begin{aligned}h_{a}:\mathbb {R} &\to (0,1)\\x\;&\mapsto {\tfrac {1}{2}}+{\tfrac {1}{2}}t(2ax)\end{aligned}}$

with $a>0$. Then $h_{a}$ is symmetric to the point (0, 1/2) and

${\begin{alignedat}{2}h_{a}&(0)&&={\tfrac {1}{2}}\\h'_{a}&(0)&&=a\\h_{a}&(-\infty )&&=0^{+}\\h_{a}&(\infty )&&=1^{-}\\\end{alignedat}}$

Negative values are mapped to values between 0 and 1/2. Positive values are mapped to values between 1/2 and 1. The parameter $a$ controls how fast the transition will be.

If we want a falling function, we can use the symmetry

$h_{a}(x)\,=1-h_{a}(-x)=1-h_{-a}(x)$

i.e. we negate $x$ or $a$.

Helper function g

$g_{a,b}\,$

This function maps the positive numbers to the interval $[0,1)$.

${\begin{aligned}g_{a,b}:\mathbb {R} ^{\geqslant \,0}&\to (0,1)\\x\;&\mapsto {\tfrac {1}{2}}+{\tfrac {1}{2}}\,t(2b\cdot a\cdot u(x/a))\end{aligned}}$

for some function $u$ that is defined below. If $u$ is appropriately chosen then for $g$ the following holds

${\begin{array}{lll}g_{a,b}(0)&=&0\\g_{a,b}(\infty )&=&1\\g_{a,b}(a)&=&1/2\\g'_{a,b}(a)&=&b\\g'_{a,b}(x)&>&0{\text{ for }}x>0\end{array}}$

This means that $g_{a,b}$

• grows continuously from 0 to 1 as $x$ grows from $0$ to $\infty$
• we can control where $g$ crosses the middle between 0 and 1 by specifying parameter $a$
• we can control how fast $g$ passes the point $(a,1/2)$ by specifying parameter $b$

We are left with determining the finction $u$ on $\mathbb {R} ^{>0}$ with

$u\,$

$u$ must satisty

${\begin{array}{lll}u(0^{+})&=&-\infty \\u(\infty )&=&\infty \\u(1)&=&0\\u'(1)&=&1\end{array}}$

For $u$ we set

$u(x)={\tfrac {1}{2}}\left(x-{\tfrac {1}{x}}\right)$

Another choice for $u$ might be $u(x)=\ln(x)$. Note that $u(x)=-u(1/x)$.

Helper function w

$w_{a}\,$

This function maps the positive numbers to the interval $[0,1)$.

${\begin{aligned}w_{a}:\mathbb {R} ^{\geqslant \,0}&\to [0,1)\\x\;&\mapsto t(ax)\end{aligned}}$

By $a$ we can control its slope in the origin:

$w'(0)=\,a$

Bézier-Curves

Quadratic

Suppose we have a smooth function

${\begin{aligned}f:[t_{0},t_{1}]&\;\to \;\mathbb {R} ^{2}\\t&\;\mapsto \;(x(t),\,y(t))\\\end{aligned}}$

and like to draw an approximation of it using quadratic Béziers. Obviously, the two end points lie on ƒ and the control point lies on the crosspoint — for simplicity, we assume it exists — of the two tangents through the bounding points. In other words, we have to determine the intersection of the two lines

$g_{n}:\textstyle {\binom {x_{n}}{y_{n}}}+\lambda _{n}\cdot \textstyle {\binom {{\dot {x}}_{n}}{{\dot {y}}_{n}}}$

with canonical abbreviations like

${\dot {x}}_{n}={\tfrac {dx}{dt}}(t_{n})$

This leads to a determining equation for the λ's

${\binom {x_{0}-x_{1}}{y_{0}-y_{1}}}={\binom {-{\dot {x}}_{0}\quad {\dot {x}}_{1}}{-{\dot {y}}_{0}\quad {\dot {y}}_{1}}}{\binom {\lambda _{0}}{\lambda _{1}}}$

whose solution is

${\binom {\lambda _{0}}{\lambda _{1}}}={\frac {1}{{\dot {x}}_{1}{\dot {y}}_{0}-{\dot {x}}_{0}{\dot {y}}_{1}}}{\binom {{\dot {y}}_{1}\quad -{\dot {x}}_{1}}{{\dot {y}}_{0}\quad -{\dot {x}}_{0}}}{\binom {x_{0}-x_{1}}{y_{0}-y_{1}}}$

This gives us the intersection, i.e. the control point, by evaluating one of (or the two of) the g's at the end point(s).

Cubic

Suppose we have a smooth function

${\begin{aligned}f:[t_{0},t_{1}]&\;\to \;\mathbb {R} ^{2}\\t&\;\mapsto \;(x(t),\,y(t))\\\end{aligned}}$

and like to draw an approximation of it using cubic Béziers

${\begin{aligned}b(t)&=(1-t)^{3}P_{0}+3(1-t)^{2}tP_{1}+3(1-t)t^{2}P_{2}+t^{3}P_{3}\\&=P_{0}+3(P_{1}-P_{0})t+3(P_{2}-2P_{1}+P_{0})t^{2}+(P_{3}-3P_{2}+3P_{1}-P_{0})t^{3}\\&=P_{3}+3(P_{2}-P_{3})(1-t)+3(P_{1}-2P_{2}+P_{3})(1-t)^{2}+(P_{0}-3P_{1}+3P_{2}-P_{3})(1-t)^{3}\end{aligned}}$

From the two last representations we see immediately the value of the derivatives of b in the end points. We want the first and second derivatives in the end points to point in the same direction as the derivatives of ƒ do. Thus

This method applied to the standard parametrization (cos t, sin t) of a quarter of the unit circle (in black):
We get the coordinates (1, 1/2) and (1/2, 1) for the control points (red). The resulting bézier (orange) does not approximate the circle as good as possible.

${\begin{aligned}\alpha \cdot {\dot {f}}_{0}&=P_{1}-P_{0}\\\beta \cdot {\dot {f}}_{1}&=P_{3}-P_{2}\\\gamma \cdot {\ddot {f}}_{0}&=P_{0}-2P_{1}+P_{2}\\\delta \cdot {\ddot {f}}_{1}&=P_{1}-2P_{2}+P_{3}\\\end{aligned}}$

and together with ƒ₀=P₀ and ƒ₁=P₃ we get the linear system

${\begin{pmatrix}-2{\dot {x}}_{0}&-{\dot {x}}_{1}&-{\ddot {x}}_{0}&0\\-2{\dot {y}}_{0}&-{\dot {y}}_{1}&-{\ddot {y}}_{0}&0\\{\dot {x}}_{0}&2{\dot {x}}_{1}&0&-{\ddot {x}}_{1}\\{\dot {y}}_{0}&2{\dot {y}}_{1}&0&-{\ddot {y}}_{1}\end{pmatrix}}\cdot {\begin{pmatrix}\alpha \\\beta \\\gamma \\\delta \end{pmatrix}}={\begin{pmatrix}x_{0}-x_{1}\\y_{0}-y_{1}\\x_{1}-x_{0}\\y_{1}-y_{0}\end{pmatrix}}$

Note that in the special case of x(t) = t we get

$\alpha =\beta ={\tfrac {1}{3}}(t_{1}-t_{0})$

i.e. the x-coordinates of the control points P₁ and P₂ divide the interval [t₀,t₁] with ratios 1:2 resp. 2:1. This is quite astonishing because in order to get the control points we do not have to evaluate second derivatives of ƒ. This is due to properties of Bernstein polynomials.

To solve the above system we use standard technique like the adjugate.

Also note that if both second derivatives of x or both second derivatives of y happen to vanish the above system won't have full rank, i.e. the corresponding matrix won't be invertible. However, it's sufficient to determine α and β to get the control points and for vanishing second derivatives we get the less complicated systems

${\begin{pmatrix}-2{\dot {x}}_{0}&-{\dot {x}}_{1}\\{\dot {x}}_{0}&2{\dot {x}}_{1}\end{pmatrix}}\cdot {\binom {\alpha }{\beta }}={\binom {x_{0}-x_{1}}{x_{1}-x_{0}}}\qquad {\text{ if }}{\ddot {x}}_{0,1}=0$

resp.

${\begin{pmatrix}-2{\dot {y}}_{0}&-{\dot {y}}_{1}\\{\dot {y}}_{0}&2{\dot {y}}_{1}\end{pmatrix}}\cdot {\binom {\alpha }{\beta }}={\binom {y_{0}-y_{1}}{y_{1}-y_{0}}}\qquad {\text{ if }}{\ddot {y}}_{0,1}=0$

Solving this yields

${\binom {\alpha }{\beta }}={\frac {1}{3}}(x_{1}-x_{0}){\binom {{\dot {x}}_{0}}{{\dot {x}}_{1}}}\qquad {\text{ if }}{\ddot {x}}_{0,1}=0$

and ditto for y.

---

As you can see in the image above, there is some room for improvement and therefore we work out a second approach. Again, we set P₀=ƒ₀, P₃=ƒ₁ and constrain the two control points P₁ resp. P₂ to lie on the tangent through the end point next to it. This leaves us again with a two dimensional space to search in. Instead of imposing properties on second derivative, we now simply force the bézier to meet the curve ƒ in a third point Q, i.e. we set

$Q=f_{t}=f(t\cdot t_{0}+(1-t)\cdot t_{1})\quad {\stackrel {.}{=}}\quad b_{[P_{0},P_{1},P_{2},P_{3}]}(t)$

for some t in (0,1) and b denoting the bézier. The condition on the end and control points again reads as

This method applied to the standard parametrization (cos t, sin t) of a quarter of the unit circle (in black):
We get the coordinates (1, ω) and (ω, 1) for the control points (red) with
   ${\scriptstyle \omega ={\frac {4}{3}}({\sqrt {2}}-1)}$
The resulting bézier approximation (orange) is fine. There is no visual difference between the circle and the bézier. The additional point Q is indicated halfway on the bow.

${\begin{aligned}P_{0}&=f_{0}\\P_{1}&=f_{0}+\alpha \cdot {\dot {f}}_{0}\\P_{2}&=f_{1}-\beta \cdot {\dot {f}}_{1}\\P_{3}&=f_{1}\\\end{aligned}}$

Putting this together with the condition on Q we get

${\begin{aligned}&{\binom {x_{t}-x_{0}}{y_{t}-y_{0}}}+(2t^{3}-3t^{2}){\binom {x_{1}-x_{0}}{y_{1}-y_{0}}}\\&\qquad \qquad =3t(1-t){\binom {(1-t){\dot {x}}_{0}\quad -t{\dot {x}}_{1}}{(1-t){\dot {y}}_{0}\quad -t{\dot {y}}_{1}}}{\binom {\alpha }{\beta }}\end{aligned}}$

Note that we can use more than one point Q. Suppose we like to use n points Q_i to guide the bézier. Each Q_i will add two more lines in the above linear system, i.e. the system will look like

$w=M\!\cdot \!{\tbinom {\alpha }{\beta }}$

with a 2n-dimensional vector w and a 2n×2 matrix M. In general, this system is overdetermined and thus has no solution. Therefore, we solve the 2-dimensional system

$M^{\top }w=M^{\top }\!M\!\cdot \!{\tbinom {\alpha }{\beta }}$

instead which yields a least-square solution for α and β.

We make the above system a little bit more explicit for the case of one additional point at t = 1/2. The linear sysstem then reduces to

${\binom {\alpha }{\beta }}={\frac {4}{3}}\,{\frac {1}{{\dot {x}}_{1}{\dot {y}}_{0}-{\dot {x}}_{0}{\dot {y}}_{1}}}{\binom {{\dot {y}}_{1}\quad -{\dot {x}}_{1}}{{\dot {y}}_{0}\quad -{\dot {x}}_{0}}}{\binom {x_{0}+x_{1}-2x_{1/2}}{y_{0}+y_{1}-2y_{1/2}}}$

Note that the same matrix already occured in the computation for quadratic bézier curves above, however the matrix now gets multiplied with a vector describing the curvature, whereas in the quadratic case it gets multiplied with a vector descriping the direction.

If the special case of a linear function x we get

$\alpha =\beta ={\frac {4}{3}}\cdot {\frac {y_{0}+y_{1}-2y_{1/2}}{{\dot {y}}_{1}-{\dot {y}}_{0}}}$

noname

Suppose we have a smooth function

${\begin{aligned}f:[t_{0},t_{3}]&\;\to \;\mathbb {R} ^{2}\\t&\;\mapsto \;(x(t),\,y(t))\\\end{aligned}}$

from the reals to the plane and like to draw an approximation of it using cubic Béziers.

Let u be a second function with fixed points at t₀ and t₃ which is smooth and monotone. Then the composition ƒ o u will yield exactly the same plot for any such u. Applying function u means that drawing the curve at different, arbitrarily increasing and descreasing speeds does not change the way the plot of the curve looks like. That is nice from the plotter's point of view. However, this generates some difficulties when we try to approximate the curve, which eventially turns out to be a playing field for calculus of variations that will lead to formulas and partial differential equations much too complex for practical considerations. So we look for some characteristics that are invariant under reparameterisations u.

The derivative of ƒ o u is the velocity

$v={\frac {\mathrm {d} }{\mathrm {d} t}}(f\circ u)={\dot {f}}\circ u\cdot {\dot {u}}$

This furmula is the rationale why the first derivative of the bézier curve shall point in the same direction as the first derivative of ƒ: the direction is independent of the parametrisation u. The speed v always points into the same direction, no matter how fast we drive along ƒ. This is no more true for the acceleration

$a={\dot {v}}={\frac {\mathrm {d} ^{2}}{\mathrm {d} t^{2}}}(f\circ u)={\dot {f}}\circ u\cdot {\ddot {u}}\,+\,{\dot {u}}^{2}\!\cdot \!{\ddot {f}}\circ u$

In the remainder of the essay we will only use properties of the curve at its end points. Thus, before we proceed, let's use the fact that u has fixed points in the t-valueas that yield the end points in order so simplify the formulas for v and $a$. The formulas then read

$v={\dot {f}}\cdot {\dot {u}}\quad {\text{ and }}\quad a={\dot {f}}\cdot {\ddot {u}}\,+\,{\dot {u}}^{2}\!\cdot \!{\ddot {f}}$

provided we evaluate these quandities at one of the end points.

We can think of $a$ as being composed of two orthogonal components: one in direction of motion that speeds up or slows down the pencil, and on perpendicular to v which leads to a change in direction. The projection of $a$ onto the direction normal to v is parallel to

${\begin{aligned}\langle a,v^{\bot }\rangle \cdot v^{\bot }&=\langle a,{\tbinom {~{\dot {y}}}{-{\dot {x}}}}\rangle \cdot {\tbinom {~{\dot {y}}}{-{\dot {x}}}}\\&={\binom {{\ddot {x}}\,{\dot {y}}^{2}\,-\,{\ddot {y}}\,{\dot {x}}\,{\dot {y}}}{{\ddot {y}}\,{\dot {x}}^{2}\,-\,{\ddot {x}}\,{\dot {y}}\,{\dot {x}}}}\cdot {\dot {u}}^{4}\\&\parallel {\binom {{\ddot {x}}\,{\dot {y}}^{2}\,-\,{\ddot {y}}\,{\dot {x}}\,{\dot {y}}}{{\ddot {y}}\,{\dot {x}}^{2}\,-\,{\ddot {x}}\,{\dot {y}}\,{\dot {x}}}}\end{aligned}}$

$L(a,b)=\int _{a}^{b}\!{\sqrt {{\dot {x}}^{2}+{\dot {y}}^{2}}}\,\mathrm {d} t$

$K(a,b)=\int _{a}^{b}{\frac {{\dot {x}}\,{\ddot {y}}\,-\,{\dot {y}}\,{\ddot {x}}}{{\dot {x}}^{2}+{\dot {y}}^{2}}}\,\mathrm {d} t$

Sphärengleiche Linear Transforms

Given a linear transfrom in n-dimensional euklidean Space:

${\begin{aligned}A:\quad \mathbb {R} ^{n}&\;\to \;\mathbb {R} ^{n}\\x&\;\mapsto \;A\cdot x\end{aligned}}$

We call two linear transforms A and B spärengleich if they map the unit sphere to the same set:

$A\sim B\quad \Leftrightarrow \quad A\cdot D_{n}=B\cdot D_{n}\qquad {\text{with}}\qquad D_{n}=\{x\in \mathbb {R} ^{n}\;/\;|x|\leqslant 1\}$

Obviously, this ~ is an equivalence relation and we look for a representant of each equivalence class. We observe that this relation preserves the spectral norm

$A\sim B\quad \Rightarrow \quad \|A\|_{2}=\|B\|_{2}$

and that orthogonal matrices don't change the equivalence class:

$Q^{\top }Q=\mathrm {id} \quad \Rightarrow \quad A\sim A\cdot Q$

for any A. The last line is immediately clear because orthogonal transformations map spheres to themselves. The preservation of spectral norm follows from the definition of spectral norm. Let

$A=U_{A}\cdot \Sigma _{A}\cdot V_{A}^{\top }$

be the singular value decomposition (svd) of A. Then we have

$A\sim U_{A}\cdot \Sigma _{A}$

and

$A\sim B\quad \Rightarrow \quad \Sigma _{A}=\Sigma _{B}$

However, the converse is not true.

Arcsin

arccos and its asymptote $\scriptstyle {\sqrt {2(1-x)}}$ in orange.

In order to approximate arcsin and arccos if the argument is close to 1 the following expansions might be useful:

${\begin{aligned}\arccos(1-x)&={\sqrt {2x}}\cdot a(x)\\\arcsin(1-x)&={\frac {\pi }{2}}-{\sqrt {2x}}\cdot a(x)\end{aligned}}$

with a rational power series

${\begin{aligned}a(x)&=1+{\frac {1}{12}}x+{\frac {3}{160}}x^{2}+{\frac {5}{896}}x^{3}+{\frac {35}{18432}}x^{4}+{\mathcal {O}}(x^{5})\\&=1+{\frac {1}{2}}\cdot {x \over 3\cdot 2}+{\frac {1\cdot 3}{2\cdot 4}}\cdot {x^{2} \over 5\cdot 2^{2}}+{\frac {1\cdot 3\cdot 5}{2\cdot 4\cdot 6}}\cdot {x^{3} \over 7\cdot 2^{3}}+\cdots \\&=\sum _{j=0}^{\infty }{\binom {2j}{j}}{\frac {x^{j}}{(2j+1)8^{j}}}\end{aligned}}$

The radius of convergence of a is 2. We start by observing that

$\arccos(1-x)=2\arcsin {\bigl (}{\sqrt {x/2}}{\bigr )}$

which can easily verified by differentiaton. It follows that

${\begin{aligned}a(x)={\arccos(1-x) \over {\sqrt {2x}}}={\arcsin({\sqrt {x/2}}) \over {\sqrt {x/2}}}=\sum _{j=0}^{\infty }{\binom {2j}{j}}{\frac {x^{j}}{(2j+1)8^{j}}}\end{aligned}}$

Also note the following half-argument relations for –2 ≤ x ≤ 2:

${\begin{aligned}2\arcsin(x/2)&=\operatorname {sgn}(x)\arccos(1-x^{2}/2)\\2\arccos(x/2)&=\pi -\operatorname {sgn}(x)\arccos(1-x^{2}/2)\end{aligned}}$

Dobble Spot It

Dobble is a card game to have a nice time with fast pattern recognition. Each card shows 8 different icons, and any two cards have exactly one icon in common. The task is to find this common icon as fast as possible.

This essay is about how such a deck of cards can be constructed, and it supplies some mathematical background. As Dobble is famous about that mathematical background, we won't get too much into the theory as many arcticels found on the net address the background. A deck of card consists of 55 cards each showing 8 different icons out of a set of 57 icons. So how do we have to arrange these icons on the cards so that any two card picked at random have exactly one icon in common?

The property

any two cards have exactly one icon in common

reminds of a theorem in plane geometry:

any two different lines in the plane meet in exactly one point

Well, almost. In Euclidean geometry there are lines in the plane that don't meet, namely parallel lines. The way out is projective projective geometry which comes without that shortcoming. Whereas points in the Euclidean plane can be regarded as pairs of numbers (x,y), points in the projective plane are triples (x : y : z) such that not all three are equal to zero. In addition, we consider two triples P and P' as the same if they are multiples of each other, i.e. if there is a number λ ≠ 0 such that

$(x:y:z)=(\lambda x':\lambda y':\lambda z')$

A line g in the plane is given by a triple (g_x : g_y : g_z) and a point P = (x : y : z) is incident on the line provided

$g_{x}x+g_{y}y+g_{z}z=0$

This is similar to the Euclidean case where a point is incident on a line if

$g_{x}x+g_{y}y+g_{z}=0$

but in projective space the additional symmetry in the formulae for the point-on-a-line relation has its counterpart in the additional symmetry of any two distinct lines meet in exactly one point. Notice that if z ≠ 0 we can divide the projective condition by z, and the outcome is basically the condition for Euclidean space. However, in the projective case there are also points with z = 0 which don't have a counterpart in Euclidean geometry. These points are sometimes called the horizon or points at infinity, but we don't need such fuzzy wording or any distinction of different classes of points to construct a deck of Dobble.

The second difference to ordinary geometry is that a deck of cards consists only of finitely many items: a finite number of icons, a finite number of cards, and a finite number of icons per card. This is handled by considering geometry over a finite field instead of geometry over the Reals. A field is an entity which features addition and multiplication, both commutative and connected by the distributive law. The addition of any element can be undone, and the element that doesn't change the result of an addition is called zero and denoted as 0. The multiplication with any element except 0 can be undone, and the element that doesn't change the result of a multiplication is called one and denoted as 1.

So let's switch to a finite field F with Q elements. The first observation is that there are only finitely many points in the plane. There are Q³ triples of the form (x : y : z) with x, y and z in F. As not all three coordinates shall be zero, we are left with Q³−1 non-zero triples. Triples which are a multiple of each other are regarded as the same point, and because there are Q−1 non-zero values in F which can serve as the factor λ from above, we get the total number of points of the projective plane over the finite field F of order Q as

${\frac {Q^{3}-1}{Q-1}}=Q^{2}+Q+1$

This is also the number of lines in that plane because the lines are also represented as triples. In order to see how many points are incident on each line, let's enumerate the points as

$(0:0:1),\;(0:1:z){\text{ and }}(1:y:z)$

If the x-coordinate is non-zero, we can divide all coordinates by x which gets us the points of the form (1 : y : z). If x is zero and y is non-zero, then divide by y to get the points of the form (0 : 1 : z). If both x and y are zero, that point can be represented as (0 : 0 : 1) because z must be non-zero then.

In order to compute which points are incident on which line, we could just do brute force and iterate over all lines and all points and test whether the relation from above is satisfied. But we can do better by working out explicit formulae. To that end we use a different relation to determine whether a point is incident on a line:

$g_{x}z+g_{y}y+g_{z}x=0$

This is just a rearrangement of points which does not change the global structure. The advantage is that in our enumeration of points and lines, the first coordinates, i.e. x and g_x, are always 0 or 1 which will simplify the computation.

Lines and Points incident on it

Line g = (gx : gy : gz)	Constraint(s) on coordinates of P	P = (x : y : z)	Case
$(0:0:1)$	$x=0$	$(0:0:1),\;(0:1:z)$	(1)
$(0:1:g_{z})$	$y+g_{z}x=0$	$(0:0:1),\;(1:-g_{z}:z)$	(2)
$(1:g_{y}:g_{z})$	$z+g_{y}y+g_{z}x=0$	$(0:1:-g_{y}),\;(1:y:-g_{z}-g_{y}y)$	(3)

In either case, there are Q+1 points on each line, and it's easy to verify that any two distinct lines have exactly one point in common. Due to the duality of points and lines, each point is incident on Q+1 different lines.

The case Q = 2

Image 1

Let's work out the simplest case of Q = 2, the Fano plane. We expect 2²+2+1 = 7 lines and hence also 7 points, each line consisting of 2+1 = 3 points, and each point incident on 3 lines.