Showing posts with label conditioning number. Show all posts
Showing posts with label conditioning number. Show all posts

Thursday, December 8, 2016

The conditioning number of a helix, part 2

Recall the previous attempt to find the conditioning number of a helix (see post "The conditioning number of a helix, part 1," 2016-10-31). Here we complete the approach and although exact solutions are hard to find, we give close approximations.

The setting was a helix $C$ of radius $r$ and stretch $c$, so given as the zero locus of $x-r\cos(z/c)$ and $y-r\sin(z/c)$, and we wanted to find where the normal plane at a point $p\in C$ intersects $C$ again. It may intersect $C$ several times, but we are only interested in the shortest distances. Without loss of generality, assume that $p=(r,0,0)$. The normal plane at $p$ is then given by
\[
0 =
\det\begin{bmatrix}
x-r\cos(p_z/c) & y-r\sin(p_z/c) & z-p_z \\
1 & 0 & r\sin(p_z/c)/c \\
0 & 1 & -r\cos(p_z/c)/c
\end{bmatrix}
=
\det\begin{bmatrix}
x-r & y & z \\
1 & 0 & 0 \\
0 & 1 & -r/c
\end{bmatrix}
=
\frac rc y + z.\]Since the cylinder on which the helix $C$ lies is $x^2+y^2=r^2$, the curve $C'$ representing the intersection of the plane with the cylinder is given by the zero locus of $\pm r\sqrt{x^2-r^2} + cz$. This allows us to find the intersection with the helix. However, since $C$ is parametrized with $z$ the free variable and $C'$ with $x$ free, its is easier to switch to cylindrical coordinates
\[
\left(r = \sqrt{x^2+y^2},\theta = \arctan(y/x), z = z\right).\]Doing so gives a nice description of $C$ and $C'$ as below.\[
\begin{array}{r l c l}
C : &  (r\cos(z/c),r\sin(z/c),z) & = & (r,\theta,\theta c) \\
C' : &  (x,-\sqrt{r^2-x^2},r\sqrt{r^2-x^2}/c) & = & (r.\theta,r^2\sin(\theta)/c)
\end{array}\]The switch in coordinates is represented by the diagram below, where we have only used the top half of $C'$.
Finding $C\cap C'$ is equivalent to solving $\frac{c^2}{r^2} = \frac{\sin(\theta)}\theta$ for $\theta$, a task that can not be solved exactly. Instead we take the tangent lines to $C'$ on the unrolled cylinder at its base, and see where those intersect the line $\theta c$. Inspecting the areas of the tangent lines closer and calculating the euclidean distances in $\R^3$ from $p$ to $a$ and $b$, which is, I can't believe I'm saying this, a great exercise for the reader, we get the distances to be
\[
d(p,a) = \sqrt{2r^2\left(1+\cos\left(\frac{\pi c^2}{r^2-c^2}\right)\right) + \left(\frac{\pi cr^2}{r^2-c^2}\right)^2},
\hspace{.2cm}
d(p,b) = \sqrt{2r^2\left(1-\cos\left(\frac{2\pi c^2}{r^2+c^2}\right)\right) + \left(\frac{2\pi c r^2}{r^2+c^2}\right)^2}.\]Truthfully, the diagrams are tricky to draw in TikZ and I don't want to simply have a scan of some rough work. More importantly, $d(p,a) = d(p,b)$ implies $c = r/\sqrt 3$, meaning that when the stretch $c$ is larger than $r/\sqrt 3$, the normal planes certainly do not intersect the helix again.

Monday, October 31, 2016

The conditioning number of a helix, part 1

Definition: Let $M$ be a smooth $d$-manifold embedded in $\R^n$ and $N^\epsilon_pM = N_pM \cap B(p,\epsilon)$ the natural embedding of the $\epsilon$-normal plane at $p\in M$. The pairwise conditioning number of $p$ and $q$ is
\[
\tau_{p,q} = \sup\{\epsilon \ :\ N^\epsilon_pM\cup N^\epsilon_qM\text{ embeds in }\R^n\}.
\]

The condition on $\epsilon$ is the same as saying $i(N^\epsilon_pM)\cap i(N^\epsilon_qM) = \emptyset$, where $i$ is induced by the embedding of $M$. It is immediate that $\tau = \inf_{p,q}\{\tau_{p,q}\}$, so we will try to find $\tau_{p,q}$ first. Recall that a helix of radius $r$ and vertical period $2\pi c$ is a 1-dimensional manifold
embedded in $\R^3$ as the zero locus of
\[
f(x,y,z) = x-r\cos(z/c),
\hspace{2cm}
g(x,y,z) = y-r\sin(z/c).
\]
We first find the normal plane at two arbitrary points $p_1,p_2$ on the helix, then their intersection (which is a line), and then the distance from $p_1$ and $p_2$ to that line. The smallest of these two distances bounds $\tau_{p_1,p_2}$ from below (and the bound is achieved on pairs of points defining the medial axis). Then take the infimum of this value over all points on the helix. However, this excludes the case when the normal planes are parallel (for instance when the two points have the same $x$- and $y$-values).

Moreover, even just calculating the infimum for points whose normal planes are not parallel yields a result of zero. We describe the process nonetheless. For the first step, we need the equations of the normal planes. Let
\[
D^f = \begin{bmatrix} 1 & 0 & r\sin(z/c)/c \end{bmatrix},
\hspace{2cm}
D^g = \begin{bmatrix} 0 & 1 & -r\cos(z/c)/c \end{bmatrix}.
\]
be the Jacobians of $f$ and $g$. The points $p_1$, $p_2$ are completely described by the $z$-coordinate, so we have two values $z_1$, $z_2$ for $p_1$, $p_2$, respectively. The normal plane at $p_i$ is the zero locus of
\[
\det\begin{bmatrix}
x-r\cos(z_i/c) & y-r\sin(z_i/c) & z-z_i \\ 1 & 0 & r\sin(z_i/c)/c \\ 0 & 1 & -r\cos(z_i/c)/c
\end{bmatrix}  = z - z_i - \frac{xr}c \sin(z_i/c) + \frac{yr}c\cos(z_i/c).
\]
We have two equations and three unknowns, so one independent variable. Solving for $x$ and $y$ gives us
\[
x = \frac{(z-z_1)\cos(z_2/c) - (z-z_2)\cos(z_1/c)}{r\sin(\frac{z_1-z_2}c)/c},
\hspace{1cm}
y = \frac{(z-z_1)\sin(z_2/c) - (z-z_2)\sin(z_1/c)}{r\sin(\frac{z_1-z_2}c)/c}.
\]
These are functions of $z$, giving us two new functions
\[
h_i(z) = (x(z)-r\cos(z_i/c))^2+(y(z)-r\sin(z_i/c))^2 + (z-z_i)^2,
\]
for $i=1,2$, which, when minimized, give a lower bound for the pairwise conditioning number of $p_1$ and $p_2$. Indeed, by slowly increasing the $\epsilon$ until the $\epsilon$-normal planes at $p_1$ and $p_2$ intersect, the first point of intersection will happen on the intersection $N_{p_1}M\cap N_{p_2}M$. Hence finding the shortest distance from $p_1$ and $p_2$ to this line gives a definite lower bound. The functions $h_i$ are quadratic in $z$, and we know the function $az^2+bz+c$, for $a>0$, has minimum at $-b/2a$. The values of $h_1$ and $h_2$ at their minima are the same and equal to
\[
h_m := h_i\left(\frac{-b}{2a}\right) = \frac{2(c^2+r^2)\cos^2\left(\frac{z1-z2}{2c}\right)\left(r^2+c(z_1-z_2)\csc\left(\frac{z_1-z_2}c\right)\right)^2}{2c^2r^2+r^4+r^4\cos\left(\frac{z_1-z_2}c\right)}.
\]
A natural limit of $h_m$ to consider is $z_2\to z_1$. If any of the factors in the numerator are zero, we also get a minimum, so another limit to look for is $z_2\to cz_1$, which makes the cosine factor zero. These are
\[
\lim_{z_2\to z_1}[h_m] = \frac{(c^2+r^2)^2}{r^2},
\hspace{2cm}
\lim_{z_2\to z_1+c\pi}[h_m] = \frac{c^2\pi^2(c^2+r^2)}{4r^2},
\]
which are finite nonzero for positive values of $c$ and $r$. For the last factor, fix $z_1=0$. Then finding when the factor vanishes is equivalent to finding when $\sin(z_2/c)$ and $-z_2 c/r^2$ intersect. There are values for which this happens, and the other factors in $h_m$ are all finite at these values, so $\inf_{z\in \R}[h_i(z)]=0$. Visual confirmation is given by the cases below.
Hence this is not the best approach to calculate the conditioning number of a curve. The next attempt will be to calculate the actual pairwise conditioning number, rather than trying to bound it from below.

Tuesday, June 28, 2016

The conditioning number of a projective curve

Let $C$ be a smooth algebraic curve in $\P^2$. That is, for some homogeneous $f\in \C[x_0,x_1,x_2]$ we let $C = \{x\in \P^2\ :\ f(x)=0\}$. Describe $C$ as a manifold via the usual open sets $U_i = \{x\in \P^2\ :\ x_i\neq 0\}$ and charts
\[
\begin{array}{r c l}
\varphi_0\ :\ U_0 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_1}{x_0},\frac{x_2}{x_0}),
\end{array}
\hspace{1cm}
\begin{array}{r c l}
\varphi_1\ :\ U_1 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_0}{x_1},\frac{x_2}{x_1}),
\end{array}
\hspace{1cm}
\begin{array}{r c l}
\varphi_2\ :\ U_2 & \to & \C^2, \\\
[x_0:x_1:x_2] & \mapsto & (\frac{x_0}{x_2},\frac{x_1}{x_2}).
\end{array}
\]
Let $w=[w_0:w_1:w_2]\in \P^2$ for which $f(w)=0$. The Jacobian of $C$ at $w$ is then
\[
J_w = \left[
\left.\frac{\dy f}{\dy x_0}\right|_w \ :\  \left.\frac{\dy f}{\dy x_1}\right|_w \ :\  \left.\frac{\dy f}{\dy x_2}\right|_w
\right] \in \P^2.
\]
Assume that $\left.\frac{\dy f}{\dy x_0}\right|_w\neq 0$ and pass to $\varphi_0(U_0)$ to get the Jacobian to be
\[
J_w^0 = \left(
\frac{\dy f/\dy x_1|_w}{\dy f/\dy x_0|_w}\ ,\ \frac{\dy f/\dy x_2|_w}{\dy f/\dy x_0|_w}\right)  \in \C^2.
\]
Assume that $w_0\neq 0$, so the tangent line to $\varphi_0(C)\subset \C^2$ at $\varphi_0(w)=(w_1/w_0,w_2/w_0)$ is
\[
T_{\varphi_0(w)}= \{\varphi_0(w)+tJ_w^0\ :\ t\in \C\}\subset \C^2.
\]
A vector orthogonal to the Jacobian $J_w^0$ is
\[
\bar J_w^0 = \left(-\frac{\dy f/\dy x_2|_w}{\dy f/\dy x_0|_w}\ ,\ \frac{\dy f/\dy x_1|_w}{\dy f/\dy x_0|_w}\right) \in \C^2,
\]
so the space space normal to $T_{\varphi_0(w)}$ is given by
\[
T_{\varphi_0(w)}^\perp = \{\varphi_0(w)+t\bar J_w^0\ :\ t\in \C\}\subset \C^2.
\]

Example: Let $C\subset \P^2$ be the zero locus of $f(x_0,x_1,x_2) = x_0^2+x_1x_2-x_1x_0$. The Jacobian is $J = [2x_0-x_1:x_2-x_0:x_1]$, and as $J=0$ implies $x_0=x_1=x_2=0$, but $0\not\in\P^2$, the curve $C$ is smooth. Consider two points $w=[1:1:0],z=[2:1:-2]\in C$, at which the Jacobian is
\[
J_w = [1:-1:1]
\hspace{1cm},\hspace{1cm}
J_z = [3:-4:1].
\]
Both $w_0$ and $z_0$ are non-zero, with $\varphi_0(w)=(1,0)$ and $\varphi_0(z)=(1/2,-1)$, giving the tangent and normal spaces to be
\begin{align*}
T_{(1,0)} & = \{(1,0)+t(-1,1)\ :\ t\in \C\}, & T_{(1/2,-1)} & = \{(1/2,-1)+s(-4/3,1/3)\ :\ s\in \C\}, \\
T^\perp_{(1,0)} & = \{(1,0)+t(-1,-1)\ :\ t\in \C\}, & T_{(1/2,-1)}^\perp & = \{(1/2,-1)+s(-1/3,-4/3)\ :\ s\in \C\}.
\end{align*}
The two normal spaces intersect at $(t,s)=(1/3,-1/2)$ at distances of $1/3\cdot ||(-1,-1)|| = \sqrt 2/3\approx 0.471$ and $1/2\cdot||(-1/3,-4/3)|| = \sqrt{17}/3\approx 1.374$ from the points $\varphi_0(w),\varphi_0(z)$, respectively. Hence the conditioning number of $C$ is at most $\sqrt 2/3$.

Given a smooth projective curve and a finite set of points, this Sage code will calculate the conditioning number from that collection of points.