Can anyone estimate N such that Prob( 0 is in the convex hull of $N$ points ) >= .95  

for points uniformly scatterered in $[-1,1]^d$, $d = 2, 3, 4, 10$ ?


The application is nearest-neghbour interpolation:
given values $z\_j$ at sample points $X\_j$, and a query point $P$,
one chooses the $N$ $X\_j$ nearest to $P$ ($N$ fixed) and averages their $z\_j$.
If $P$ is not in the convex hull of the $N$ $X\_j$,
the interpolation will be one-sided, not so good.  

I'd like to be able to say
"taking 6 neighbors in 2d, 10 in 3d, is seldom one-sided".


If anyone could point me to selfcontained pseudocode for the function Inhull( $N$ points )
(without calling full LP), that would be useful too.


(Please add tags interpolation convex-geometry ?)



Estimate probability( 0 is in the convex hull of N random points ) ?
This is a classical and essentially geometric problem. In fact, *the answer does not depend 
on the distribution of the points* (as long as the distribution is centrally symmetric). 


The following result is due to Wendel ([link](http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=wendel&s5=A%2520problem%2520in%2520geometric%2520probability&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq)).



> 
> **Theorem.** If $X\_1$, ..., $X\_N$ are i.i.d. random points in $R^d$ whose distribution
>  is symmetric with respect to $0$ and assigns measure zero to every hyperplane
>  through $0$, then
>  $$\mathbb P(0\notin \mbox{conv}\{X\_1,\dots,X\_N\})=\frac{1}{2^{N-1}}\sum\limits\_{k=0}^{d-1}{N-1 \choose k}.$$
> 
> 
> 


The proof is straightforward. Let $\mu$ be the distribution of $X\_k$, and set
$$ f(x\_1,\dots,x\_N) = \begin{cases} 1, & \mbox{if } x\_1,\dots,x\_N\ \mbox{ lie in an open halfspace of $\mathbb R^d$ with $0$ in the boundary}, \newline 0, & \mbox{else.} \end{cases}$$
Then due to the invariance of $\mu$ under reflection in the origin, we have that
$$\mathbb P(0\notin \mbox{conv}\{X\_1,\dots,X\_N\})=\int\_{\mathbb R^d}\dots \int\_{\mathbb R^d} \frac{1}{2^N}\sum\limits\_{\varepsilon\_i=\pm1}f(\varepsilon\_1x\_1,\dots,\varepsilon\_Nx\_N)\ \mu(dx\_1)\dots\mu(dx\_N).$$
Now, the sum
$$C(N,d)=\sum\limits\_{\varepsilon\_i=\pm1}f(\varepsilon\_1x\_1,\dots,\varepsilon\_Nx\_N)$$
can be interpreted as the number of connected components of the set $\mathbb R^d\backslash (H\_1\cup\dots\cup H\_N)$ induced by the hyperplanes $H\_1$, ..., $H\_N$ through $0$ which are in general position. But there is a classical calculation going back to to Steiner and Schläfli, which shows that
$$C(N,d)= 2\sum\limits\_{k=0}^{d-1}{N-1 \choose k}.$$ 


