User thilo schneider - MathOverflow

Maximum distance of points in intersection of balls

2011-05-11T13:32:06Z

Dear all,

let $B_\delta(p):=\{x\in\mathbb{R}^d:||x-p||_2\leq \delta\}$ be a $d$-dimensional closed ball.

Now I do not have one ball, but four: $B_{r_1}(p)$, $B_{r_2}(p)$, $B_{s_1}(q)$ and $B_{s_2}(q)$. Furthermore, the following properties hold:

$r_1+s_1\geq ||p-q||_2$ , thus $B_{r_1}(p)\cap B_{s_1}(q)\neq \emptyset$,
$r_2+s_2\geq ||p-q||_2$ , thus $B_{r_2}(p)\cap B_{s_2}(q)\neq \emptyset$.

Now I want to get an expression for

\[ \sup_{x\in B_{r_1}(p)\cap B_{s_1}(q)}\quad \sup_{y\in B_{r_2}(p)\cap B_{s_2}(q)} \quad ||x-y||_2. \]

I have been racking my head over it, but I do not find an elegant solution. If nothing else helps, I could only solve the problem for $d=2$ and represent the hull of the balls in parametric form and do some minimization there. But I would rather like a more general approach.

Here a small drawing of one of the scenarios that might happen: The distance of interest here is between the upper intersection of the two red balls ($B_{r_1}(p)$ and $B_{s_1}(p)$) and the lower intersection of the two black balls. Roughly measured, this equals 3.

Any help would be welcome. Thanks in advance.

Answer by Thilo Schneider for Could this be a NP complete?

2011-05-07T21:44:39Z

Just a rough idea: (I am not really an expert on graph theory, so there may be a much better upper bound.)

You can group the vertices according to their distance to $s$, say

$L_i=\{v\in V|dist(s,v)=i\}$

Then of course the $L_i$ are pairwise disjoint. Any shortest path from $s$ to a given vertex $v$ has to pass the $L_i$ ascending (you can easily proof this fact), so first a vertex from $L_1$, then one from $L_2$, and so on. That means there are at most $\prod_{i=1}^{dist(s,v)-1}|L_i|$ shortest paths. As $|L_i|\leq |V|$, you have a polynomial upper bound.

While thinking about it: There might be a way to press this bound much lower, as $|L_i|=|V|$ only happens when all vertices have distance 1, which means the shortest path is the direct connection between $s$ and $v$. For decreasing amount of vertices in the $L_i$, the possible length of the path grows. You probably could use this to get a better bound.

I do not see why the rest of your algorithm should not work.

Answer by Thilo Schneider for Minimum norm of convex hull

2011-05-05T21:13:14Z

Dear all,

I think I found quite a neat solution for my problem. At first I want to give humble thanks to Roland, who greatly inspired the solution I'm going to use now. Just in case somebody else might sometimes in the future be struggling with a similar problem, I'm going to give a short outline of the ideas and a rough sketch of the algorithm. After some consideration I decided to go down to only two dimensions, as this allows some neat tricks.

To go along with the notation I use in my own work (and which I did not use asking the question), let $X=\{x_1,\ldots, x_n\}$ be the set that spans the convex hull $H$.

First I want to reflect the main ideas, which I am certain are very obvious to most of you.

Let $P=\arg\min_{x\in H}||x||_2^2$. It is either $P\in H$ and thus $P=0$, or $P$ lies on the boundary of $H$, which means there are $x,'x\in X$ and $c\in[0,1]$ with $P=cx+(1-c)x'$.
Let now \[ \delta:=\min_{i=1,\ldots,n}\min_{j=i+1,\ldots, n}\min\left\{||x||_2^2: x=cx_i+(1-c)x_j, c\in[0,1]\right\}. \] Because of 1. we have $\min_{x\in H}||x||_2^2\in{0,\delta}$.
To compute $\delta$, a lot of minimum norms $d$ on line segments from $x_i$ to $x_j$ have to be computed. By usage of the scalar product and simple usage or pythagoras, one can derive the distance as \[ d=\begin{cases} ||x_i||^2_2 & \text{if } \langle x_i,x_i-x_j\rangle \leq 0\\ ||x_j||^2_2 & \text{if } \langle x_i,x_i-x_j\rangle \geq ||x_i-x_j||_2^2\\ ||x_i||^2_2-\frac{\langle x_i, x_i-x_j\rangle^2} {||x_i-x_j||^2} & \text{ otherwise}. \end{cases} \]
The point $P$ realizing the minimum distance in this case is \[ P=x_i+\frac{(x_j-x_i)\langle x_i, x_i-x_j\rangle}{||x_i-x_j||_2^2} \]
Given $\delta$ and the Point $P$ realizing $\delta$, the following holds: $0\in H$ if and only if there exists $x_k$ with $\langle P, P-x_k\rangle >0$. (Very compact proof: If one of those exists, one can reduce $\delta$ by using the method of 3. As the new minimum may not lie on the boundary as it has not been found in the first run, $0\in H$ has to hold. Otherwise assume $0\in H$ and no scalar product fulfills the given condition. Then one can write $0$ as convex combination of the $x_i$ and express $0<||P||_2^2=\langle{P,P-0}\rangle$ and, using linearity of the scalar product, show that this is $\leq 0$ and thus getting a contradiction).

Putting all of this together one yields the following algorithm:

Init $d_\min = \infty$.
For $i\in\{0,\ldots, n-1\}$ do:
1. Compute $n_i$ = $||x_i||_2^2$
2. For ($j \in \{i+1,\ldots, n-1\}$ do
  1. Compute $s_{i,j}=\langle x_i, x_j\rangle$.
  2. Compute $n_j=||x_j||_2^2$ .
  3. Decide:
    - If $s_{i,j}\geq n_i$ set $d=n_i, c=1$.
    - If $s_{i,j}\geq n_j$ set $d=n_j, c = 0$.
    - Else set $c = (n_i-s_{i,j})/(n_i+n_j-2s_{i,j})$ and $d=n_i- (n_i-s_{i,j})\cdot c$.
  4. If $d<d_{\min}$ set $d_{\min}= d$, $j_{\min}= j$, $i_{\min} = i$ and $c_{\min} = c$.
For $k\in\{0,\ldots,n\}\setminus\{i,j\}$ do: If $d > (1-c)s_{i,k}+c s_{j,k}$ return 0.
Return $d_\min$.

This algorithm is based on the rules 1-5 above, however, the conditions are formulated a bit more efficient. Please apologize the incomplete reasoning. I found this solution appealing as it allows a lot of optimization in my special scenario. I already computed all norms of the $x_i$ somewhere else, so this is no further effort. Furthermore, the parent algorithm scans a set of values, successively replacing one $x_i$ with another $x_i'$ and then again computing the distance to the convex hull. This means that most of the distances can be saved and used later and for each iteration I only have to do very little work in updating and computing very few (as for my main problem, where $n=4$ it is 3) scalar products.

Thank you for your support and the in fact very valuable input.

Minimum norm of convex hull

2011-05-03T16:44:15Z

Dear all,

I am currently stuck at a problem which seems too easy to be stuck at to me...

Summary

Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute \[\min_{x\in H}||x||^2_2 \] efficiently?

Conditions one should know about

When I talk about efficiency in this question, I do not talk about a polynomal time algorithm. For my purpose, $n$ is really small, $n=4$ should do in almost all cases. (Even a fast solution for the special case $n=4$ would be highly appreciated). Also, $d=2$ is the main dimension of interest, whereas it might be possible that at some time this might also be a question for the three dimensional space. This question is embedded in an algorithm that will be called thousands of times within a very short timeframe. In short, I am looking for an efficient way in terms of "Do I need 20 or 40 FLOPS"...

First thoughts

Of course, one could take this problem as a Quadratic Program by writing $D=[d_1,\ldots, d_n]$ and then minimizing $x^tD^tDx$ with respect to $\sum_{i=1}^d x= 1$ and $x_i\geq 0$. However, I just feel this might be overkill for such a simple problem.

I also thought about taking a least norm approach, but here I do not really get a grip on formulating the problem the right way to throw some (to me) known technique at it.

Also, one could compute the convex hull explicitly and then try to locate 0 geometrically around the hull and only compute the corresponding distance to the hull. As I made a rough sketch to the algorithm I had in mind, I realized this also gives me quite a lot of things to compute and cases to distinguish between.

Your ideas would be greatly appreciated.

Comment by Thilo Schneider

2011-05-11T18:20:47Z

Thank you. Looks promising at a first glance. I will have a more in-depth look tomorrow and give feedback accordingly.

Comment by Thilo Schneider

2011-05-11T16:07:59Z

Thanks for the input! However, I am afraid your solution does not work. Look at the example I included above. There we have $r_2=2$, $||p-q||=5$ and $s_2=4$, thus $d_{p1}=9$ and $d_{q1}=7$. This results in $d_{11}=|5-9-7|=11$. The geometrically obtained solution should be roughly 3, so $d_{11}$ already is to big. I do not see your reasoning right now, which makes it hard to see if this is simply a typo or a problem with the logic.

Comment by Thilo Schneider

2011-05-05T20:10:15Z

Thanks for the input. I believe I found an algorithm that should work faster for my specific problem (which is not intended for the GPU - at least not yet).

Comment by Thilo Schneider

2011-05-04T06:36:22Z

@Sergei: Thank you for pointing out. Currently I assume you can easily rescue Rolands algorithm without increasing the computational effort a lot. Will give feedback once I am more certain (a.k.a once I got my idea proven).

Comment by Thilo Schneider

2011-05-04T05:29:13Z

@Anadim: It does not have to be one of the $d_i$-points if $0\not\in H$. The searched point could also lie on any line segment between $d_i$ and another $d_j$ (assuming they both lie on the boundary of the convex hull). Also note that while finding the Point in $H$ closes to the origin solves the problem, I am only interested in the minimum distance.

Comment by Thilo Schneider

2011-05-03T20:20:06Z

Thank you. Looks promising at a first glance. I will have a more in depth look tomorrow and will probably accept your answer then.