2
$\begingroup$

Let $n_1,\cdots,n_m$ be unit vectors arbitrarily chosen in $\mathbb{R}^3$. Then, there exist some optimal unit vector $n$ such that $$|n^Tn_i|\geq \delta(m)>0 \quad \forall i=1,2,\cdots,m$$ I am looking for a lower bound on $\delta(m)$ for all possible configurations of $n_1,\cdots,n_m$.

For example if $m=2$, then it appears that $\delta(2)\geq \sin(\pi/4)$ (the worst case is when they are normal). Obviously, $\delta$ decreases as $m$ increases.

Edit: I am describing an attempt that appears promising. The set of all points that are normal to each vector $n_i$ define a great circle (GC) on the unit sphere. These are the points to be avoided by $n$. Thus there are $m$ such GCs. Assume now that we add these GCs one by one. Each one added can intersect every one of the existing ones in 2 points at most. Those intersections define new regions on the sphere surface. Thus the upper bound on the number of regions is $2+2+2\cdot 2+\cdots+2\cdot (m-1)=m^2-m+2$. enter image description here Selecting the vector $n$ to lie on the center of the region that has the maximum distance from each edges is the optimal placement for $n$. A fact that can be exploited is that since the overall area is $4\pi$ there exists one region with area greater than or equal to $4\pi/(m^2-m+2)$.

For the case of $m=3$ vectors the situation is more simple. In this case the regions are 8 spherical triangles and we can prove that there exists one with lengths greater than or equal to $\pi/2$ on all edges.

enter image description here Choosing the center of this triangle as the direction of $n$ yields the desired solution.

$\endgroup$
3
  • $\begingroup$ I fear that an exact result is out of reach because it is connected to the difficult issue of optimal placement of $m$ points on the (unit) sphere for a general $m$. $\endgroup$
    – Jean Marie
    Apr 9, 2017 at 11:02
  • $\begingroup$ @JeanMarie Thank you for your comment. I understand this, therefore what I am looking for is just a lower bound not an exact optimal. Alternatively, this question can be viewed as follows: Each vector $n_i$ defines a great circle that must be avoided. The intersections of all these $m$ great circles define spherical triangles over the unit sphere. What I am looking is to prove that one can find such a triangle with a center that differs by some minimal angle from all the points on the edges. $\endgroup$
    – RTJ
    Apr 9, 2017 at 11:10
  • $\begingroup$ If you are looking for an approximate solution, why dont you consider linear programming (known as "the simplex method") ? $\endgroup$
    – Jean Marie
    Apr 9, 2017 at 11:18

2 Answers 2

2
$\begingroup$

We can widen your great circles by $\phi$ on each side to make a band around the sphere. If we make $\phi$ small enough the total area of the bands will be less than $4 \pi$ and there must be at least one direction that is more than $\phi$ from being normal to every unit vector. That will give the lower bound you seek. The band comprises the whole sphere less two spherical caps of angle $\frac \pi 2 - \phi=\theta$ (to match the $\theta$ in the Wikipedia article) so its area is $4\pi \cos \theta$ We want $m 4\pi cos \theta \lt 4 \pi$ or $\cos \theta \lt \frac 1m$ We can therefore guarantee that $\delta(m) \gt \frac 1m$. You can improve this some by considering the overlap of the bands, which reduces the covered area and would allow increasing $\cos \theta$

$\endgroup$
1
  • $\begingroup$ Great! You are the best! $\endgroup$
    – RTJ
    Apr 9, 2017 at 21:45
1
$\begingroup$

This issue is a "maximin" (maximize a minimum value) issue.

Such an optimal vector always exists, due to the fact that

  • the sphere $S$ is a compact subset of $\mathbb R^3$ and

  • function $$f: \ (x,y,z) \ \to \ min_i(|a_ix+b_iy+c_iz|)$$

is continuous,

thus reaches its maximum for some $(x,y,z)=(x_0,y_0,z_0)$.

I fear that an exact result is out of reach because it is connected to the difficult issue of optimal placement of $m$ points on the (unit) sphere for a general $m$.

$\endgroup$
3
  • $\begingroup$ What I need is a sub-optimal theoretical lower bound on this max-min problem i.e. it suffices to find some form of $\delta(m)>0$ such that $\max f(x^*)>\delta(m)>0$. I don't see how to attack this with linear programming. since I am not looking to compute the optimal but only to find a theoretical lower bound (I need this in another proof I am working). Note that this must hold for all possible configurations of $(a_i,b_i,c_i)$. $\endgroup$
    – RTJ
    Apr 9, 2017 at 11:30
  • $\begingroup$ I understand. Are you with a general $m$ or does it belong to a certain range of values ? $\endgroup$
    – Jean Marie
    Apr 9, 2017 at 11:34
  • $\begingroup$ Thank you for your time. Ideally it would be nice to prove some bound for general $m$. $\endgroup$
    – RTJ
    Apr 9, 2017 at 11:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .