Trigonometry/spherical angles/minimum-least-squares [closed]

Question

An issue from 3D tessellated geometry: Find the direction vector of a plane that minimizes the silhouette of a set of triangles. To say it another way, find the direction vector that is most perpendicular to a set of triangles. Each triangle area is half of the length of the normal vector of any two sides—call it $n_i$. The projected area is simply the dot product of these face vectors with the target plane normal, $a$. Some of these could be negative, so we square and sum—this is a minimal least squares problem: minimize. $$ f(a)=\sum_i (a \cdot n_i)^2 \text{ over all } a \in \mathbb{S}_2. $$ This could be done with constrained optimization by creating a Lagrangian, but this seems to lead to a set of nonlinear equations. Instead, use the spherical angles and redefine $a$ as: $$ a = [\cos\phi \sin\theta, \sin\phi \sin\theta, \cos\theta] $$ The derivative of the gradient of $f$ could be set to zero and we solve for the angles: $\phi$ and $\theta$. Here are those two equations: $$ \frac{df}{d\phi} =2(x_{ni} \cos\phi \sin\theta+y_{ni}\sin\phi \sin\theta +z_{ni}\cos\theta)(y_{ni}\sin\theta \cos\phi-x_{ni}\sin\theta sin\phi)=0 $$ $$ \frac{df}{d\theta}=2(x_{ni} \cos\phi \sin\theta+y_{ni}\sin\phi \sin\theta +z_{ni}\cos\theta)((x_{ni}\cos\phi+y_{ni}\sin\phi)\cos\theta-z_{ni}\sin\theta)=0 $$

Now, here's where I get confused! I essentially have two terms on the left hand sides that could be zero in each equation. Given that the first big term $(x_{ni} \cos\phi \sin\theta+y_{ni}\sin\phi \sin\theta +z_{ni}\cos\theta)$ is the same in both equations, this being zero won't help us since our equations will reduce to one. and we need two to solve for the two variables ($\phi$ and $\theta$).

The latter two parenthetical terms then make for some nice equations that we can reduce to: $$\phi = \arctan(y_{ni} / x_{ni})$$ and $$\theta = \arctan((x_{ni}\cos\phi+y_{ni}\sin\phi) / z_{ni})$$

Gee, I'm smart! I code this up and give it a try where the sum of normals results in: $x_{ni} = 500; y_{ni}= -800; z_{ni} = -0.06$. Clearly the answer should be mostly in the $z$-direction but as you can see from these last two equations, it is clearly not! Where did I go wrong?

Answer 1

If you use constrained optimization, you do get linear equations. I set $g(x)=||x||^2$. For every $x \in \mathbb{R}^3$, $$\nabla f(x) = \sum_i 2(x \cdot n_i)n_i \text{ and } \nabla g(x) = 2x.$$ You look at (unit) vectors $x$ such that $\nabla f(x) = \lambda \nabla g(x)$ for some real number $\lambda$, namely you look at eigenvectors of the symmetric endomorphism $u$ given by $$u(x) = \sum_i (x \cdot n_i)n_i.$$ Actually, using an orthogonal basis of eigenvectors of $u$, you get that the minimum of $f(x) = x \cdot u(x)$ over all $x \in \mathbb{S}_2$ is achieved when $x$ is an eigenvector associated to the least eigenvalue of $u$.

This can be proved directly. Call $\lambda_1 \le \lambda_2 \le \lambda_3$ the eigenvalues of $u$ and call $(e_1,e_2,e_3)$ an orthonormal basis of associated eigenvectors. Then for every $x = \xi_1e_1+\xi_2e_2+\xi_1e_3 \in \mathbb{R}^3$, $$f(x) = x \cdot u(x) = \sum_{i=1}^3 \lambda_i\xi^2 \ge \sum_{i=1}^3 \lambda_1\xi^2 = \lambda_1||x||^2,$$and equality holds when $x$ is a multiple of $e_1$.