User thilo schneider - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T19:24:42Z http://mathoverflow.net/feeds/user/14865 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64607/maximum-distance-of-points-in-intersection-of-balls Maximum distance of points in intersection of balls Thilo Schneider 2011-05-11T13:32:06Z 2011-05-11T17:30:48Z <p>Dear all,</p> <p>let $B_\delta(p):=\{x\in\mathbb{R}^d:||x-p||_2\leq \delta\}$ be a $d$-dimensional closed ball.</p> <p>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:</p> <ul> <li><code>$r_1+s_1\geq ||p-q||_2$</code>, thus $B_{r_1}(p)\cap B_{s_1}(q)\neq \emptyset$,</li> <li><code>$r_2+s_2\geq ||p-q||_2$</code>, thus $B_{r_2}(p)\cap B_{s_2}(q)\neq \emptyset$.</li> </ul> <p>Now I want to get an expression for</p> <p>$\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.$</p> <p>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.</p> <p>Here a small drawing of one of the scenarios that might happen: <img src="http://img571.imageshack.us/img571/3015/ballintersection.jpg" alt="Example Drawing"> 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.</p> <p>Any help would be welcome. Thanks in advance.</p> http://mathoverflow.net/questions/64233/could-this-be-a-np-complete/64236#64236 Answer by Thilo Schneider for Could this be a NP complete? Thilo Schneider 2011-05-07T21:44:39Z 2011-05-07T21:44:39Z <p>Just a rough idea: (I am not really an expert on graph theory, so there may be a much better upper bound.)</p> <p>You can group the vertices according to their distance to $s$, say</p> <p>$L_i=\{v\in V|dist(s,v)=i\}$</p> <p>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. </p> <p>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.</p> <p>I do not see why the rest of your algorithm should not work.</p> http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull/64055#64055 Answer by Thilo Schneider for Minimum norm of convex hull Thilo Schneider 2011-05-05T21:13:14Z 2011-05-05T21:13:14Z <p>Dear all,</p> <p>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. </p> <p>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$. </p> <p>First I want to reflect the main ideas, which I am certain are very obvious to most of you. </p> <ol> <li>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'$. </li> <li>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}$.</li> <li>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 &amp; \text{if } \langle x_i,x_i-x_j\rangle \leq 0\\ ||x_j||^2_2 &amp; \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} &amp; \text{ otherwise}. \end{cases}$</li> <li>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}$</li> <li>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&lt;||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).</li> </ol> <p>Putting all of this together one yields the following algorithm:</p> <hr> <ol> <li>Init $d_\min = \infty$.</li> <li><p>For $i\in\{0,\ldots, n-1\}$ do:</p> <ol> <li>Compute $n_i$ = $||x_i||_2^2$</li> <li>For ($j \in \{i+1,\ldots, n-1\}$ do <ol> <li>Compute $s_{i,j}=\langle x_i, x_j\rangle$.</li> <li>Compute <code>$n_j=||x_j||_2^2$</code>.</li> <li>Decide: <ul> <li>If $s_{i,j}\geq n_i$ set $d=n_i, c=1$. </li> <li>If $s_{i,j}\geq n_j$ set $d=n_j, c = 0$.</li> <li>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$.</li> </ul></li> <li>If <code>$d&lt;d_{\min}$</code> set $d_{\min}= d$, $j_{\min}= j$, $i_{\min} = i$ and $c_{\min} = c$.</li> </ol></li> </ol></li> <li><p>For $k\in\{0,\ldots,n\}\setminus\{i,j\}$ do: If $d > (1-c)s_{i,k}+c s_{j,k}$ return 0.</p></li> <li><p>Return $d_\min$.</p></li> </ol> <hr> <p>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 <em>parent</em> 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.</p> <p>Thank you for your support and the in fact very valuable input. </p> http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull Minimum norm of convex hull Thilo Schneider 2011-05-03T16:44:15Z 2011-05-05T21:13:14Z <p>Dear all, </p> <p>I am currently stuck at a problem which seems too easy to be stuck at to me...</p> <h3>Summary</h3> <p>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?</p> <h3>Conditions one should know about</h3> <p>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 <em>efficient</em> way in terms of "Do I need 20 or 40 FLOPS"...</p> <h3>First thoughts</h3> <p>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. </p> <p>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.</p> <p>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. </p> <p>Your ideas would be greatly appreciated. </p> http://mathoverflow.net/questions/64607/maximum-distance-of-points-in-intersection-of-balls/64660#64660 Comment by Thilo Schneider Thilo Schneider 2011-05-11T18:20:47Z 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. http://mathoverflow.net/questions/64607/maximum-distance-of-points-in-intersection-of-balls/64623#64623 Comment by Thilo Schneider Thilo Schneider 2011-05-11T16:07:59Z 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. http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull/63844#63844 Comment by Thilo Schneider Thilo Schneider 2011-05-05T20:10:15Z 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). http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull/63829#63829 Comment by Thilo Schneider Thilo Schneider 2011-05-04T06:36:22Z 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). http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull Comment by Thilo Schneider Thilo Schneider 2011-05-04T05:29:13Z 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. http://mathoverflow.net/questions/63826/minimum-norm-of-convex-hull/63829#63829 Comment by Thilo Schneider Thilo Schneider 2011-05-03T20:20:06Z 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.